HHot 100C++ 图解

104. 二叉树的最大深度

简单 二叉树 3 帧动画 在力扣上做

一句话套路递归 max(左高,右高)+1

题目描述

给定一个二叉树 root ,返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

 

示例 1:

 

输入:root = [3,9,20,null,null,15,7]
输出:3

示例 2:

输入:root = [1,null,2]
输出:2

 

提示:

  • 树中节点的数量在 [0, 104] 区间内。
  • -100 <= Node.val <= 100

思路

时间O(n)
空间O(h)(最坏退化成链表时 O(n))

思路

自底向上。depth = 1 + max(左深, 右深),空树为 0。

图解

9 3 15 20 7
二叉树(来自本仓库测试数据,nullopt 表示空位)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/08_binary_tree.cpp9 行
namespace lc0104 {
class Solution {
 public:
  int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q104_max_depth8 行
lc0104::Solution s;
TreeNode* a = buildTree({3, 9, 20, nullopt, nullopt, 15, 7});
CHECK_EQ(s.maxDepth(a), 3);
freeTree(a);
TreeNode* b = buildTree({1, nullopt, 2});  // 右斜链
CHECK_EQ(s.maxDepth(b), 2);
freeTree(b);
CHECK_EQ(s.maxDepth(nullptr), 0);

↑↓ 选择↵ 打开/ 随时唤起