Problem Statement
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example:
Input: root = [3,9,20,null,null,15,7]
Output: 3问题
给定一个二叉树的根节点，返回其最大深度。
二叉树的最大深度是从根节点到最远叶节点的最长路径上的节点数量。
示例：
输入: root = [3,9,20,null,null,15,7]
输出: 3解决方案 1
Approach 1 / 方法 1
Using Depth-First Search (DFS) to traverse the tree and calculate the depth.
使用深度优先搜索（DFS）遍历树并计算深度。
Detailed Steps / 详细步骤
Initialization / 初始化:
- If the tree is empty, return 0.
- 如果树为空，则返回0。
Step 1 / 第一步:
- Recursively find the depth of the left subtree.
- 递归找到左子树的深度。
Step 2 / 第二步:
- Recursively find the depth of the right subtree.
- 递归找到右子树的深度。
Step 3 / 第三步:
- The depth of the current node is the maximum of the depths of its left and right subtrees plus one.
- 当前节点的深度是其左右子树深度的最大值加一。
Implementation / 实现
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)
return max(left_depth, right_depth) + 1Explanation / 解释
- Step 1 / 第一步:
- Check if the root is null, return 0 if true.
- 检查根节点是否为空，如果是则返回0。
- Step 2 / 第二步:
- Recursively find the maximum depth of the left subtree.
- 递归地找到左子树的最大深度。
- Step 3 / 第三步:
- Recursively find the maximum depth of the right subtree.
- 递归地找到右子树的最大深度。
- Step 4 / 第四步:
- Return the greater depth between left and right subtrees plus one.
- 返回左子树和右子树之间的较大深度加一。
Complexity Analysis / 复杂度分析
Time Complexity: O(n)
- We visit each node exactly once.
- 我们对每个节点只访问一次。
Space Complexity: O(h)
- The space complexity is O(h), where h is the height of the tree. This space is used for the recursion stack.
- 空间复杂度为O(h)，其中h是树的高度。这些空间用于递归栈。
Key Concept / 关键概念
Recursion
- The solution leverages recursion to traverse the tree and calculate depths.
- 解决方案利用递归遍历树并计算深度。
解决方案 2
Approach 2 / 方法 2
Using Breadth-First Search (BFS) to traverse the tree level by level.
使用广度优先搜索（BFS）逐层遍历树。
Detailed Steps / 详细步骤
Initialization / 初始化:
- Use a queue to facilitate level order traversal.
- 使用队列来实现层次遍历。
Step 1 / 第一步:
- Initialize the depth to 0.
- 初始化深度为0。
Step 2 / 第二步:
- While the queue is not empty, increment the depth for each level.
- 当队列不为空时，每层递增深度。
Step 3 / 第三步:
- Add the children of the nodes at the current level to the queue.
- 将当前层节点的子节点添加到队列中。
Implementation / 实现
from collections import deque
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
queue = deque([root])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depthExplanation / 解释
- Step 1 / 第一步:
- Initialize a queue with the root node.
- 初始化一个包含根节点的队列。
- Step 2 / 第二步:
- Initialize depth to 0.
- 将深度初始化为0。
- Step 3 / 第三步:
- While the queue is not empty, process each level and increment depth.
- 当队列不为空时，处理每一层并增加深度。
- Step 4 / 第四步:
- For each node at the current level, add its children to the queue.
- 对于当前层的每个节点，将其子节点添加到队列中。
Complexity Analysis / 复杂度分析
Time Complexity: O(n)
- We visit each node exactly once.
- 我们对每个节点只访问一次。
Space Complexity: O(n)
- The space complexity is O(n) for the queue in the worst case.
- 队列在最坏情况下的空间复杂度为O(n)。
Key Concept / 关键概念
Iteration with BFS
- This solution leverages a queue for iterative level order traversal.
- 该解决方案利用队列进行迭代层次遍历。
Tips / 提示
- Recursion can be simple but may cause stack overflow for very deep trees.
- 递归很简单，但对于非常深的树可能会导致堆栈溢出。
- BFS can handle very deep trees more efficiently.
- BFS可以更高效地处理非常深的树。
Solution Template for similar questions / 提示
- Understand the tree traversal techniques (DFS and BFS).
- 理解树遍历技术（DFS和BFS）。
- Practice with different tree structures to solidify understanding.
- 通过不同的树结构进行练习以巩固理解。
Recommended 5 more similar questions / 推荐5问题
- LeetCode 111: Minimum Depth of Binary Tree
- LeetCode 543: Diameter of Binary Tree
- LeetCode 226: Invert Binary Tree
- LeetCode 110: Balanced Binary Tree
- LeetCode 257: Binary Tree Paths
More
Maximum Depth of Binary Tree – 3 Solutions – Leetcode 104 – Python NeetCode
Leave a Reply