网站主题风格,wordpress设置缩略图,专业网站建设新闻,不要营业执照的做网站【二叉树】No. 0124 二叉树中的最大路径和 【困难】#x1f449;力扣对应题目指路 希望对你有帮助呀#xff01;#xff01;#x1f49c;#x1f49c; 如有更好理解的思路#xff0c;欢迎大家留言补充 ~ 一起加油叭 #x1f4a6; 欢迎关注、订阅专栏 【力扣详解】谢谢你…【二叉树】No. 0124 二叉树中的最大路径和 【困难】力扣对应题目指路 希望对你有帮助呀 如有更好理解的思路欢迎大家留言补充 ~ 一起加油叭 欢迎关注、订阅专栏 【力扣详解】谢谢你的支持 ⭐ 题目描述二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。 路径和 是路径中各节点值的总和 示例 输入root [-10,9,20,null,null,15,7] 输出42 解释最优路径是 15 - 20 - 7 路径和为 15 20 7 42 思路需要结合左、右孩子的情况确定以当前节点为中间点时的最优路径和所以采用 后续遍历 当前节点 node 为中间点时的最优路径和由 node.val left_result right_result 计算获得 left_result 和 right_result 计算时仅能选择其左、右孩子中的一个 ⭐题目准备之后续遍历:一定要先掌握后续遍历 ❗❗❗ 放在最后面啦供不熟悉的友友参考~ 参考如上思路给出详细步骤如下 步骤一⭐确定递归函数 traversal 参数及返回值 参数需要根据当前节点 current… 计算当前节点 node 为中间点时的最优路径和 temp_max node.val left_result right_result 【 重要】 漏掉这一步的话会误解如【本文开头示例】所示的情况 计算当前节点 node 为单侧中继点时的部分最优路径和 node.val max(left_result, right_result) 返回值当前节点 node 为单侧中继点时的部分最优路径和 步骤二⭐确定递归终止条件 走到了 None 节点步骤三⭐确定单层递归逻辑-后序处理根据左、右子树的递归返回值情况确定当前节点的返回值 # 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 __init__(self):self.max -1000def maxPathSum(self, root: Optional[TreeNode]) - int:def traversal(node): # ------------------------------------- step 1if node None: return 0 # ---------------------------- step 2# ------------------------------------------------------- step 3left_result max(traversal(node.left),0)right_result max(traversal(node.right),0)temp_max node.val left_result right_result ## 【 重要】self.max max(self.max, temp_max)return node.val max(left_result, right_result) ## traversal(root)return self.max ⭐⭐⭐ 题目准备之后续遍历:一定要先掌握后续遍历 ❗❗❗ # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def lowestCommonAncestor(self, root, p, q)::type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNodeself.result []def traversal(current):if current None:returnprint(-------------------------Hi, node: , current.val)traversal(current.left)traversal(current.right)print(----- current_val: , current.val) // 观察此处的处理顺序是后序self.result.append(current.val)traversal(root) ## self.result: [6, 7, 4, 2, 5, 0, 8, 1, 3]对应的输出结果如下(-------------------------Hi, node: , 3)
(-------------------------Hi, node: , 5)
(-------------------------Hi, node: , 6)
(----- current_val: , 6)
(-------------------------Hi, node: , 2)
(-------------------------Hi, node: , 7)
(----- current_val: , 7)
(-------------------------Hi, node: , 4)
(----- current_val: , 4)
(----- current_val: , 2)
(----- current_val: , 5)
(-------------------------Hi, node: , 1)
(-------------------------Hi, node: , 0)
(----- current_val: , 0)
(-------------------------Hi, node: , 8)
(----- current_val: , 8)
(----- current_val: , 1)
(----- current_val: , 3) 希望对你有帮助呀 如有更好理解的思路欢迎大家留言补充 ~ 一起加油叭 LeetCode 热题 HOT 100
