What is the maximum depth of a binary tree?

The maximum depth of a binary tree is the number of nodes along the longest path from the root node to a leaf node.

How do you calculate the maximum depth using DFS?

In DFS, you recursively traverse both the left and right subtrees, comparing the depths, and return the maximum depth encountered plus one for the current node.

Can you solve Maximum Depth of Binary Tree using BFS?

Yes, BFS iteratively explores each level of the tree, incrementing the depth with each level processed, ensuring the maximum depth is found after visiting all nodes.

What are the common pitfalls when solving Maximum Depth of Binary Tree?

Common pitfalls include failing to handle empty trees, confusing depth with the number of nodes, and not managing recursion depth in DFS for large trees.

How does state tracking help in the maximum depth problem?

State tracking ensures that you keep track of the current depth as you traverse the tree, allowing for an efficient and accurate calculation of the maximum depth.

#104

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。示例 1：输入： root = [3,9,20,null,null,15,7] 输出： 3 示例 2：输入： root = [1,null,2] 输出： 2 提示：树中节点的数量…

树深度优先搜索广度优先搜索二叉树

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

lightbulb

解题思路

方法一：递归

递归遍历左右子树，求左右子树的最大深度，然后取最大值加 $1$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 是二叉树的节点数。每个节点在递归中只被遍历一次。

1

2

3

4

5

6

7

8

9

10

11

12

13

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        l, r = self.maxDepth(root.left), self.maxDepth(root.right)
        return 1 + max(l, r)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand how to traverse a tree using both DFS and BFS approaches?
question_mark
Can you describe how state tracking in traversal ensures the correct calculation of the tree's maximum depth?
question_mark
Will you be able to explain the time and space complexity trade-offs between DFS and BFS for this problem?

warning

常见陷阱

外企场景

error
Failing to handle edge cases, such as an empty tree (null root).
error
Confusing tree depth with the number of nodes or height of the tree.
error
Not considering the impact of recursion depth in DFS when working with large trees.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the minimum depth of a binary tree (minimum number of nodes along a path).
arrow_right_alt
Determine if a binary tree is balanced (the depths of the two subtrees of every node differ by no more than 1).
arrow_right_alt
Implement a solution to find the diameter of a binary tree (the longest path between any two nodes).

help

常见问题

外企场景

继续练习

#101 对称二叉树 #100 相同的树 #111 二叉树的最小深度