124. Binary Tree Maximum Path Sum

Question: Binary Tree Maximum Path Sum

Solution

思路：

1. 要找 path 的最大值 → DFS

2. root 最大值的算法是：node + 左邊總和最大 + 右邊總和最大 所以要往下知道 left & right children 總和的最大值。
   要得知 left child 的最大值，一樣要往下知道 left child 的 left & right children 的值 → Recursive Function

3. Recursive Function 要可以回傳該 node 目前算出的最大值

4. 而該 node 的最大值可能會有三種：

   1. node 本身：因為如果 left / right node 是負數，就會把總合拉低
   2. node + 左邊總和最大
   3. node + 右邊總和最大

   從上面三個值選出最大，return

5. 最後，path 的算法可以是 node + 左邊最大 + 右邊最大，所以每次在 node ，計算以上三種情況時，也要把 path 的計算考慮進去，但是不用回傳，只需要另外用一個變數紀錄即可。只要加總是最大，就把變數記起來。

Recursive Function: dfs(node)

• 終止條件：
  • 如果 node == None，代表走到底了，return 0: if node == None: return 0
• 遞回條件：
  • left_max = dfs(node.left)
  • right_max = dfs(node.right)
  • 計算此 node path 的值: node.val + left_max + right_max
  • 在 node 本身，node + left, node + right, node + left + right 中選出最大: max_val = max(node.val, node.val + left_max + right_max, node.val + left_max, node.val + right_max)
  • return max(node.val, node.val + left_max, node.val + right_max)

TimeComplexity: O(n)

# 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 maxPathSum(self, root: Optional[TreeNode]) -> int:

max_val = [root.val]

def dfs(node):

if node == None:

return 0

left_max = dfs(node.left)

right_max = dfs(node.right)

node_max = max(node.val, node.val + left_max + right_max, node.val + left_max, node.val + right_max)

max_val[0] = max(max_val[0], node_max)

return max(node.val, node.val + left_max, node.val + right_max)

dfs(root)

return max_val[0]

Video Solution