提升网站性能,水果商城的设计与实现,嵌入式和网站开发,高端网站建设多少钱104. 二叉树的最大深度
已解答
简单
相关标签
相关企业
给定一个二叉树 root #xff0c;返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1#xff1a; 输入#xff1a;root [3,9,20,null,null,15,7]
输出#xff1a;3…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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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。
