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)
思路
- 使用递归方法计算二叉树的最大深度。
- 二叉树的最大深度可以表示为:
- 如果节点为空(即
root == None
),那么深度为 0。 - 否则,树的最大深度为左子树和右子树的最大深度加 1。
- 如果节点为空(即
- 递归地计算左右子树的深度,并返回它们的最大值加 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]
:
- 根节点
3
的左子树深度为 1,右子树深度为 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 的优点是,它逐层访问节点,可以在找到最远叶子节点时直接得出最大深度。
- 从根节点开始,将其加入队列,并初始化深度为 0。
- 每一层的节点都会被处理,并在遍历该层的所有节点后,深度增加 1。
- 当队列为空时,说明所有层都遍历完了,此时的深度就是树的最大深度。
代码实现
以下是 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]
:
- 第一层只有根节点
3
,深度为 1。 - 第二层有节点
9
和20
,深度增加到 2。 - 第三层有节点
15
和7
,深度增加到 3。 - 遍历完所有层,最终返回深度
3
。