跳到主要内容

LeetCode 104. 二叉树的最大深度

本节目标

让每棵子树返回自身高度，在当前节点取较大值后加一。

这道题是子树信息与递归判断的起点：一棵子树只需向父节点报告自己的高度。

查看 LeetCode 原题

题意与边界​

最大深度是从根到最远叶子的节点数。空树没有节点，深度为 0；单节点树的深度为 1。这个空树定义恰好让叶子节点由两个零高度子树得到高度 1。

子树高度返回值​

令 maxDepth(node) 表示以 node 为根的子树高度。左右子树已经各自返回高度后，当前子树的高度就是两者较大值加一。返回值既是父节点需要的信息，也是根节点调用时的最终答案。

正确性依据​

对树结构归纳。空树按定义返回 0。若左右子树调用分别返回正确高度，任何经过当前根的根到叶路径都会先进入其中较深的一侧，再经过当前节点，因此当前高度为两者最大值加一。故根调用得到整棵树的最大深度。

代码实现​

C++17
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

复杂度分析​

每个节点恰好访问一次，时间复杂度为 O(n)。递归调用栈深度为树高 h，额外空间为 O(h)。

易错点​

  • 把空树返回 1，会使叶子深度多算一层。
  • 只递归某一侧，会漏掉另一侧更深的叶子。
  • 把高度按边数计算；本题要求的是节点数。

模式迁移​

当父节点还要知道子树是否失败时，可在高度返回值中增加失败状态；当当前节点需要更新一条穿过自己的路径时，则保留高度返回值并另外维护答案。