124.Binary Tree Maximum Path Sum
===

###### tags: `Hard`,`Tree`,`Binary Tree`,`DFS`,`DP`

[124. Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/)

### 題目描述

A **path** in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence **at most once**. Note that the path does not need to pass through the root.

The **path sum** of a path is the sum of the node's values in the path.

Given the `root` of a binary tree, return *the maximum **path sum** of any **non-empty** path*.

### 範例

**Example 1:**


Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

**Example 2:**


Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

**Constraints**:

* The number of nodes in the tree is in the range [1, 3 * 10^4^].
* -1000 <= `Node.val` <= 1000

### 解答
#### C++

class Solution {
public:
    int dfs(TreeNode* node, int& ans) {
        if (!node) return 0;
        int L = max(0, dfs(node->left, ans));
        int R = max(0, dfs(node->right, ans));
        ans = max(ans, node->val + L + R);
        return max(L, R) + node->val;
    }
    int maxPathSum(TreeNode* root) {
        int ans = INT_MIN;
        dfs(root, ans);
        return ans;
    }
};

> [name=Yen-Chi Chen][time=Sun, Dec 11, 2022]

#### Python

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def dfs(node, ans):
            if not node: return 0
            L = max(dfs(node.left, ans), 0)
            R = max(dfs(node.right, ans), 0)
            ans[0] = max(ans[0], node.val + L + R)
            return node.val + max(L, R)
        ans = [float('-inf')]
        dfs(root, ans)
        return ans[0]

> [name=Yen-Chi Chen][time=Sun, Dec 11, 2022]

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if not root: return 0
            left = dfs(root.left)
            right = dfs(root.right)
            self.ans = max(self.ans, max(root.val + left + right, root.val + left, root.val + right, root.val))
            return max(root.val, root.val + max(left, right))

        self.ans = -math.inf
        dfs(root)
        return self.ans

> 很容易一直 WA 的題目
> [name=Kobe][time=Mon, Dec 12, 2022]

#### C#

public class Solution {
    public int MaxPathSum(TreeNode root) {
        MaxPathSumFromRoot(root, out int maxSum);
        return maxSum;
    }

    private int MaxPathSumFromRoot(TreeNode node, out int maxPathSum) {
        if (node == null) {
            maxPathSum = int.MinValue;
            return 0;
        }

        int left = MaxPathSumFromRoot(node.left, out int leftMax);
        int right = MaxPathSumFromRoot(node.right, out int rightMax);
        
        maxPathSum = Max(node.val + left + right, leftMax, rightMax);

        return Max(node.val + Max(left, right), 0);
    }

    private int Max(params int[] numbers) {
        return Enumerable.Max(numbers);
    }
}

> [name=Jim][time=Mon, Dec 12, 2022]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)