Leetcode題解 Python & C#：四月挑戰DAY29 Binary Tree Maximum Path Sum

給一串非空的二元樹，找出最大的路徑總和。

如果要使用遞迴的想法：以尋找當前的節與左右兩邊子樹最大的路徑，可以找到通過該節的最大路徑。

如果要住上傳，那會是左右或零取大者加自身再上傳。

因此遞迴函數要有兩種：
1.回傳值是到該點的最大路徑。
2.由1.得到左右最大的路徑，去計算通過該點的最大路徑。

Python

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.result = root.val
        def dfs(node):
            if not node: return 0
            rsum = dfs(node.right)
            lsum = dfs(node.left)
            maxPath = node.val+max(0, rsum, lsum)
            self.result = max(maxPath, node.val+lsum+rsum, self.result)
            return maxPath              
        dfs(root)
        return self.result

C#

public class Solution {    
    public int result;
    
    public int MaxPathSum(TreeNode root) {
        result = root.val;
        dfs(root);
        return result;
    }
    
    public int dfs(TreeNode node)
    {
        if(node is null){return 0;}    
        var values = new int[2];
        int rsum = dfs(node.right);
        int lsum = dfs(node.left);
        values[0] = Math.Max(node.val + rsum, node.val + lsum);
        values[0] = Math.Max(node.val, values[0]);
        values[1] = node.val + lsum + rsum;
        result = Math.Max(Math.Max(values[0],values[1]),result);
        return values[0];
    }
}