binary-tree-maximum-path-sum(mock)

注意：

// 注意,如果一个类放在另一个类里面,初始化时候会报错 Solution is not a enclosing class
// 这是因为如果TreeNode不是static,那么要求先有外部类的实例
// 要加上static
// 或者放到类的外面

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);

    }

}