0124. Binary Tree Maximum Path Sum - chasel2361/leetcode GitHub Wiki

***Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections.
The path must contain at least one node and does not need to go through the root.

Example 1:
Input: [1,2,3]
Output: 6

Example 2:
Input: [-10,9,20,null,null,15,7]
Output: 42

一開始我題目沒看清楚，以為是要從根開始找最大的路徑和，還想說這個難度也可以叫做 hard 喔，明明就不難啊，只要在分支上先比較左右子樹的大小，往大的那邊加過去就可以了，寫出來的程式碼長這樣

class Solution:
    def __init__(self):
        self.total = 0
    def maxPathSum(self, root: TreeNode) -> int:
        if not root: return 0
            
        self.total += root.val
        if not root.left and not root.right:
            return self.total
        if not root.left and root.right:
            self.maxPathSum(root.right)
        if not root.right and root.left:
            self.maxPathSum(root.left)
                
        if root.left.val > root.right.val:
            self.maxPathSum(root.left)
        else:
            self.maxPathSum(root.right)
        return self.total

結果試跑一遍後才發現是任選兩個點找最大路徑和，靠北

---

如果我們要找兩個節點間的路徑和，這個路徑必定經過他們兩個共同的最低祖先節點 (或稱中繼點)，最大路徑和就會是：

    max(中繼點值, 左子樹最大路徑和 + 中繼點, 右子樹最大路徑和 + 中繼點值, 三者總和)

所以只要用遞迴的方式依序比較每個節點，遇到更大的就更新，便可以解決這個問題。不過另一個問題是，左子樹以及右子樹的最大路徑和該怎麼計算出來呢？
可以這樣表示：

    max(節點值, 左子樹最大路徑和 + 節點值, 右子樹最大路徑和 + 節點值)

使用這些概念後寫出來的程式碼會長這樣

[1] 紀錄此節點不為中繼點時的最大路徑和
[2] 比較此節點為與不為中繼點時的最大路徑和，以及目前最大路徑和
[3] 回傳不為中繼點時的最大路徑和

class Solution:
    def __init__(self):
        self.res = 0
            
    def maxPathSum(self, root: TreeNode) -> int:
        if not root: return 0
        self.res = root.val
        self.dfs(root)
        return self.res
        
    def dfs(self, node):
        l = self.dfs(node.left) if node.left else 0
        r = self.dfs(node.right) if node.right else 0
        m = max(node.val, node.val + l, node.val + r)  #[1]
        self.res = max(self.res, m, l + r + node.val)  # [2]
        return m  # [3]

由於這個遞迴函式會一路優先往深層走，所以會稱為深度優先搜尋 (DFS, DeepFirst search)

這個寫法的時間複雜度以及空間複雜度都是 O(N)

• 最糟的時候要從最左下比較最右下才會出現最大值，遞迴的層數為N