python 网站开发书籍百度站内搜索 wordpress

104. 二叉树的最大深度

已解答

简单

相关标签

相关企业

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

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

示例 1：

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

示例 2：

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

提示：

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

 方法一：后序遍历（DFS）

思路

1. 使用递归方法计算二叉树的最大深度。
2. 二叉树的最大深度可以表示为：
   • 如果节点为空（即 root == None），那么深度为 0。
   • 否则，树的最大深度为左子树和右子树的最大深度加 1。
3. 递归地计算左右子树的深度，并返回它们的最大值加 1。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int maxDepth(TreeNode root) {if (root == null ){return 0;}else{return Math.max(maxDepth(root.left),maxDepth(root.right))+1;}}
}

思路与算法

如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为

max(l,r)+1

复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树中的节点数。因为我们每个节点都需要访问一次。
• 空间复杂度：O(H)，其中 H 是二叉树的高度。在最坏情况下（树完全倾斜），递归栈的深度可能会达到树的高度。

示例

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

1. 根节点 3 的左子树深度为 1，右子树深度为 2。
2. 因此，最大深度为 2 + 1 = 3。

# 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: Optional[TreeNode]) -> int:# 如果节点为空，深度为 0if root is None:return 0# 递归求左右子树的深度left_depth = self.maxDepth(root.left)right_depth = self.maxDepth(root.right)# 返回左右子树较大深度加 1return max(left_depth, right_depth) + 1

方法 2：迭代 DFS（使用栈）

可以用栈来实现 DFS，从根节点开始，将每个节点和对应的深度存入栈中，然后更新最大深度。

代码如下：

class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:# 特殊情况处理if root is None:return 0# 使用栈来进行 DFS，每个元素是 (节点, 深度)stack = [(root, 1)]max_depth = 0# 开始 DFSwhile stack:node, depth = stack.pop()if node:# 更新最大深度max_depth = max(max_depth, depth)# 将左右子节点及其深度加入栈stack.append((node.left, depth + 1))stack.append((node.right, depth + 1))return max_depth

方法二：层序遍历（BFS）

树的层序遍历 / 广度优先搜索往往利用 队列 实现。

关键点： 每遍历一层，则计数器 +1 ，直到遍历完成，则可得到树的深度。

在计算二叉树的最大深度时，我们也可以使用广度优先搜索（BFS）来实现。BFS 会按层遍历二叉树，因此每遍历完一层，深度就增加 1。使用 BFS 的优点是，它逐层访问节点，可以在找到最远叶子节点时直接得出最大深度。

1. 从根节点开始，将其加入队列，并初始化深度为 0。
2. 每一层的节点都会被处理，并在遍历该层的所有节点后，深度增加 1。
3. 当队列为空时，说明所有层都遍历完了，此时的深度就是树的最大深度。

代码实现

以下是 BFS 的实现代码，使用 Python 的 collections.deque 来实现队列操作：

# 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: Optional[TreeNode]) -> int:# 如果根节点为空，直接返回深度 0if root is None:return 0# 初始化队列并将根节点加入队列queue = deque([root])depth = 0# 开始 BFSwhile queue:# 每一层的节点数量level_size = len(queue)# 处理当前层的所有节点for _ in range(level_size):node = queue.popleft()# 将子节点加入队列if node.left:queue.append(node.left)if node.right:queue.append(node.right)# 当前层处理完，深度加 1depth += 1return depth

复杂度分析

• 时间复杂度：O(N)，其中 N 是节点数。每个节点访问一次。
• 空间复杂度：O(W)，其中 W 是树的最大宽度。在最坏情况下，队列中最多会存储一层的所有节点数量。

示例

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

1. 第一层只有根节点 3，深度为 1。
2. 第二层有节点 9 和 20，深度增加到 2。
3. 第三层有节点 15 和 7，深度增加到 3。
4. 遍历完所有层，最终返回深度 3。