企业官网建设流程全解析

北京市企业网站建设,免费模板下载网站,图像处理专业网站,网站实施就是网站建设给定一个二叉树 root #xff0c;返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。示例 1#xff1a;输入#xff1a;root [3,9,20,null,null,15,7] 输出#xff1a;3示例 2#xff1a;输入#xff1a;root [1,null,2] 输出#…给定一个二叉树root返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。示例 1输入root [3,9,20,null,null,15,7]输出3示例 2输入root [1,null,2]输出2提示树中节点的数量在[0,]区间内。-100 Node.val 100解题思路二叉树的最大深度是 “从根节点到最远叶子节点的最长路径的节点数”递归深度优先搜索DFS利用 “分治思想”树的最大深度 左子树最大深度与右子树最大深度的较大值 1根节点本身Python代码from typing import Optional 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: # 递归终止条件空节点的深度为0 if not root: return 0 # 递归计算左、右子树的最大深度 left_depth self.maxDepth(root.left) right_depth self.maxDepth(root.right) # 当前树的最大深度 子树最大深度 1当前根节点 return max(left_depth, right_depth) 1 if __name__ __main__: sol Solution() # 示例1构建树 [3,9,20,null,null,15,7] → 预期输出3 root1 TreeNode(3) root1.left TreeNode(9) root1.right TreeNode(20) root1.right.left TreeNode(15) root1.right.right TreeNode(7) print(示例1输出, sol.maxDepth(root1)) print(预期结果3) # 示例2构建树 [1,null,2] → 预期输出2 root2 TreeNode(1) root2.right TreeNode(2) print(示例2输出, sol.maxDepth(root2)) print(预期结果2)LeetCode提交代码# 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: if not root: return 0 left_depth self.maxDepth(root.left) right_depth self.maxDepth(root.right) return max(left_depth, right_depth) 1程序运行截图展示总结本文介绍了计算二叉树最大深度的递归解法。最大深度定义为从根节点到最远叶子节点的最长路径上的节点数。采用分治思想将问题分解为计算左右子树的最大深度取较大值加1当前节点作为结果。Python实现使用深度优先搜索(DFS)递归方法当节点为空时返回0否则递归计算左右子树深度并返回较大值1。示例验证了代码的正确性如[3,9,20,null,null,15,7]输出3[1,null,2]输出2。该方法简洁高效时间复杂度O(n)。