124. Binary Tree Maximum Path Sum

# Hard, DFS

两个维度去分析这个问题

这个hard问题可以拆分成两个小问题：

1. 自根节点往下，总和最大路径

2. 左子树或右子树，总和最大路径

这是一个需要分而治之去解决的问题，需要知道哪些信息（如何分）：

1. 左边总和最大的路径，自根节点向下左边总和最大路径

2. 右边总和最大的路径，自根节点向下右边总和最大路径

3. 横跨左右包括root的最大路径

如何合并：以上三点，取最大路径

最重要是每次需要记录两个返回值。想像成每一个root要记录什么？记录自root下去总和最大路径，以及目前为止知道的总和最大路径

横跨root节点的总和最大路径怎么算？就是从左叶子下去最大路径+root+从右边叶子下去最大路径

迭代结束的终止条件：

if root=None，then return m = [0, float('-inf')]

m[0]是root下去总和最大路径，m[1]是目前为止知道的最大路径。

从根节点出发总和最大路径不仅需要比较左右向下的路径，还要与0比较，因为如果根节点以下全为负数，甚至可以不要根节点。

一定要会写test case，例如[-1], [-1, -2, -3], [1, 2].

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxPath = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        pathHelper(root);
        return maxPath;
    }
    
    public int pathHelper(TreeNode root) {
        // stop condition
        if(root == null) return Integer.MIN_VALUE;
        
        int left = pathHelper(root.left);
        int right = pathHelper(root.right);
        int singlePath = Math.max(Math.max(left, right), 0) + root.val;
        int rootPath = Math.max(left, 0) + Math.max(right, 0) + root.val;
        maxPath = Math.max(Math.max(singlePath, rootPath), maxPath);
        
        return singlePath;
    }
}

Python

// Some code
# 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:
        res = self.traversalMax(root)
        return res[0]
        
        
    def traversalMax(self, root):    # return (maxValue, maxValue_include_root)
        if root == None:
            return (float('-inf'), float('-inf'))
        
        left = self.traversalMax(root.left)
        right = self.traversalMax(root.right)
        
        maxValue_root = max(max(left[1] + root.val, right[1] + root.val), root.val)
        
        maxValue = max(max(max(left[0], right[0]), maxValue_root), left[1] + right[1] + root.val)
        
        maxValue_root = max(maxValue_root, 0)
        
        return (maxValue, maxValue_root)