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