https://leetcode.com/problems/binary-tree-maximum-path-sum/
https://leetcode.com/mockinterview/session/result/xslp8c2/
package com.company;


import java.util.ArrayList;
import java.util.List;


class Solution {

    // 注意,如果放在Solution里面,会报错 Solution is not a enclosing class
    // 这是因为如果TreeNode不是static,那么要求先有外部类的实例
    // 要加上static
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public int maxPathSum(TreeNode root) {
        // 要求至少有一个元素,全是负数情况下不能认为是0
        if (root == null) {
            return 0;
        }
        List<Integer> ret = impl(root);
        return ret.get(1);
    }

    // 多值返回一般放在容器里
    // [0]包含root的单一路径最大值; [1] 最大值;
    // 调用时保证root不会为null
    private List<Integer> impl(TreeNode root) {
        List<Integer> ret = new ArrayList();
        int maxWithRoot = root.val;
        int maxRet = root.val;

        if (root.left != null) {
            List<Integer> left = impl(root.left);
            System.out.printf("Here is left %d, ret: %d, %d\n", root.left.val, left.get(0), left.get(1));
            if (left.get(0) > 0) {
                maxWithRoot = root.val + left.get(0);
            }
            maxRet = maxWithRoot > left.get(1) ? maxWithRoot : left.get(1);

        }
        if (root.right != null) {
            List<Integer> right = impl(root.right);
            int tmp = maxWithRoot;
            if (root.val + right.get(0) > maxWithRoot) {
                maxWithRoot = root.val + right.get(0);
            }
            // 下面这个地方因为考虑不周,导致了一个bug,只考虑了maxWithRoot,没有考虑之前的maxRet
            maxRet = maxWithRoot > maxRet ? maxWithRoot : maxRet;
            maxRet = maxRet > right.get(1) ? maxRet : right.get(1);

            // merge two branch
            if (tmp + right.get(0) > maxRet) {
                maxRet = tmp + right.get(0);
            }
        }

        ret.add(maxWithRoot);
        ret.add(maxRet);
        System.out.printf("Here is node %d, ret: %d, %d\n", root.val, maxWithRoot, maxRet);
        return ret;
    }
}

public class Main {

    public static void main(String[] args) {
        // write your code here
        System.out.println("Hello");

        Solution.TreeNode node1 = new Solution.TreeNode(1);
        Solution.TreeNode node2 = new Solution.TreeNode(2);
        Solution.TreeNode node3 = new Solution.TreeNode(3);
        Solution.TreeNode node4 = new Solution.TreeNode(4);
        Solution.TreeNode node5 = new Solution.TreeNode(5);
        Solution.TreeNode node6 = new Solution.TreeNode(6);
        Solution.TreeNode node7 = new Solution.TreeNode(7);
        Solution.TreeNode node8 = new Solution.TreeNode(8);
        Solution.TreeNode node9 = new Solution.TreeNode(9);
        Solution.TreeNode node10 = new Solution.TreeNode(10);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;
        node5.left = node10;

        Solution solution = new Solution();
        int ret = solution.maxPathSum(node1);
        System.out.printf("Get ret: %d\n", ret);

    }
}