LeetCode 热题 HOT 100 （025/100）【宇宙最简朴版】

【二叉树】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 节点
  
• 步调三⭐确定单层递归逻辑-后序处置处罚：根据左、右子树的递归返回值环境，确定当前节点的返回值
  

1. # Definition for a binary tree node.
2. # class TreeNode:
3. #     def __init__(self, val=0, left=None, right=None):
4. #         self.val = val
5. #         self.left = left
6. #         self.right = right
7. class Solution:
8.     def __init__(self):
9.         self.max = -1000
10.    
11.     def maxPathSum(self, root: Optional[TreeNode]) -> int:
12.         def traversal(node):  # ------------------------------------- step 1
13.             if node == None: return 0  # ---------------------------- step 2
14.                         # ------------------------------------------------------- step 3
15.             left_result     = max(traversal(node.left),0)
16.             right_result    = max(traversal(node.right),0)
18.             temp_max = node.val + left_result + right_result  ## 【💥 重要】
19.             self.max = max(self.max, temp_max)
21.             return node.val + max(left_result, right_result)  ## 💡
23.         traversal(root)
24.         return self.max

复制代码

---

   ⭐⭐⭐ 标题准备之后续遍历:肯定要先把握后续遍历 ❗❗❗

1. # Definition for a binary tree node.
2. # class TreeNode(object):
3. #     def __init__(self, x):
4. #         self.val = x
5. #         self.left = None
6. #         self.right = None
8. class Solution(object):
9.     def lowestCommonAncestor(self, root, p, q):
10.         """
11.         :type root: TreeNode
12.         :type p: TreeNode
13.         :type q: TreeNode
14.         :rtype: TreeNode
15.         """
16.         self.result = []
18.         def traversal(current):
19.             if current == None:
20.                 return
21.             print('-------------------------Hi, node: ', current.val)
22.             traversal(current.left)
23.             traversal(current.right)
24.             print('----- current_val: ', current.val)  // 观察此处的处理顺序，是后序
25.             self.result.append(current.val)
26.         
27.         traversal(root)  ## self.result: [6, 7, 4, 2, 5, 0, 8, 1, 3]

复制代码

• 对应的输出效果如下：
  1. ('-------------------------Hi, node: ', 3)
  2. ('-------------------------Hi, node: ', 5)
  3. ('-------------------------Hi, node: ', 6)
  4. ('----- current_val: ', 6)
  5. ('-------------------------Hi, node: ', 2)
  6. ('-------------------------Hi, node: ', 7)
  7. ('----- current_val: ', 7)
  8. ('-------------------------Hi, node: ', 4)
  9. ('----- current_val: ', 4)
  10. ('----- current_val: ', 2)
  11. ('----- current_val: ', 5)
  12. ('-------------------------Hi, node: ', 1)
  13. ('-------------------------Hi, node: ', 0)
  14. ('----- current_val: ', 0)
  15. ('-------------------------Hi, node: ', 8)
  16. ('----- current_val: ', 8)
  17. ('----- current_val: ', 1)
  18. ('----- current_val: ', 3)

  复制代码

   渴望对你有资助呀！！💜💜 如有更好明白的思绪，欢迎各人留言增补 ~ 一起加油叭 💦
🔥 LeetCode 热题 HOT 100