Easy

题目描述

给定一个二叉树，找出其最大深度。

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

示例 1：

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

示例 2：

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

提示：

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

解题思路

这是一道经典的二叉树遍历问题，有多种解法：

方法一：递归（深度优先搜索）（推荐）

这是最直观的解法。对于每个节点，其最大深度等于其左右子树最大深度的较大值加1。递归的终止条件是遇到空节点，返回深度0。

递归公式：maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1

方法二：迭代（广度优先搜索）

使用队列进行层序遍历，每遍历完一层就将深度加1。需要记录每层的节点数量，确保正确统计层数。

方法三：迭代（深度优先搜索）

使用栈模拟递归过程，同时记录每个节点对应的深度。遍历过程中更新最大深度值。

递归解法代码简洁且易理解，是首选方案。对于大多数情况，递归的栈开销是可以接受的。

代码实现

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

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

public class Solution {
    public int MaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.Max(MaxDepth(root.left), MaxDepth(root.right)) + 1;
    }
}

var maxDepth = function(root) {
    if (root === null) {
        return 0;
    }
    
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度递归解法迭代解法(BFS/DFS)
时间复杂度O(n)O(n)
空间复杂度O(h)O(w)

说明：

  • n 为二叉树节点总数
  • h 为二叉树高度，最坏情况下 h = n（退化为链表）
  • w 为二叉树最大宽度，最坏情况下 w = n/2（完全二叉树的最后一层）

相关题目