路径

1. Binary Tree Maximum Path Sum
2. Path Sum III
3. Flatten Binary Tree to linked list
4. Binary Tree Longest Consecutive Sequence

1. Binary Tree Maximum Path Sum

key: bottom up + global variable / dfs + tuple info

有两种解法，不管是哪一种，都是需要保存更新2个信息：global的最大值（可以是不经过当前节点的）& local的最大值（一定得是经过当前节点的）

bottom up dfs

从 bottom-up 的角度看，这是一个从底部不停 merge 最优的子路径在根节点会和的过程。最终 return 的结果只是“必须包括当前节点” 的最大 path，由此完成连续的递归结构（recurrence substructure）

class Solution {
    int max;//需要一个全局变量来记录

    public int maxPathSum(TreeNode root) {
        if (root == null) return -1;
        max = root.val;
        bottomupDfs(root);
        return max;
    }

    private int bottomupDfs(TreeNode root) {
        if (root == null) return 0;
         // 检查两边的做大路径和，或者直接抛弃（取值为0）
        // 因此当一个小三角形一边为负数的时候
        // 最后返回的结果看起来是三个点的和，其实只是一条边
        int left = Math.max(0, bottomupDfs(root.left));
        int right = Math.max(0, bottomupDfs(root.right));

        //更新最大值，如果支路是负数，直接抛弃
        max = Math.max(max, left + right + root.val);

        // 传递到上一层的路线必须连续且不能拐弯，保持连续的递归状态
        return Math.max(left, right) + root.val;
    }
}

tuple info

比较方便给其他的tree问题套模板

class Solution {
    class Info {
        int singlePath;
        int maxPath;
        public Info(int singlePath, int maxPath) {
            this.singlePath = singlePath;
            this.maxPath = maxPath;
        }
    }

    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        return traverse(root).maxPath;
    }

    private Info traverse(TreeNode root) {
        if (root == null) return new Info(0, Integer.MIN_VALUE);
        Info left = traverse(root.left);
        Info right = traverse(root.right);
        //single path 必须得有一个节点，不拐弯
        int singleMax = Math.max(0, Math.max(left.singlePath, right.singlePath)) + root.val;
        //全局最大值，可以是左边、右边或者经过root的子树
        int max = Math.max(Math.max(right.maxPath, left.maxPath), 
                           Math.max(0, right.singlePath) + Math.max(0, left.singlePath) + root.val);
        return new Info(singleMax, max);
    }

}

2. Path Sum III

hash map: pre sum deduction

Map 储存从root到不同点得出的不同的sum，value是sum出现的次数。如果root --> current node得出的current sum - target sum得出的pre sum之前出现过，说明pre node 到 current node之间的点可以组成target sum。而且pre sum可能有好几个Node都可以得到，那么说明中间路的组合有好几种，所以要加上pre sum对应的occurence values。

Note: 需要一开始在map中放入(0, 1), denoting the starting point is from the root。