今�Hの国の呵呵君: [Algorithm]Get Path with Max Sum in Binary Tree

今�Hの国の呵呵君: [Algorithm]Get Path with Max Sum in Binary Tree
是Binary Tree Maximum Path Sum的变形, 这次是要把得到path而不是单纯的sum，解法也是类似的，只不过递归的时候return path，当在一个节点的时候，先得到左子树和右子树中最大的path，算出左边和右边的和，然后根据左边右边和自己的和判断是否需要更新最大值。然后return左边还是右边的策略和maximum path sum是一样的。T(N) = 2T(N/2) + O(N)，O(N)是每次要根据path来算出sum，根据master therom，时间复杂度为O(N log N)

    private ArrayList<Integer> res = new ArrayList<Integer>();
    private int sum = Integer.MIN_VALUE;

    public ArrayList<Integer> getPath(TreeNode root){
        getMaxPath(root);
        return res;
    }

    private ArrayList<Integer> getMaxPath(TreeNode node){
        if (node == null)
            return new ArrayList<Integer>();
        ArrayList<Integer> left = getMaxPath(node.left);
        ArrayList<Integer> right = getMaxPath(node.right);
        int leftSum = 0, rightSum = 0;
        for (int i = 0; i < left.size(); i++)
            leftSum += left.get(i);
        for (int i = 0; i < right.size(); i++)
            rightSum += right.get(i);
        if (leftSum + node.val + rightSum > sum) {
            res = new ArrayList<Integer>(left);
            res.add(node.val);
            for (int i = right.size() - 1; i >= 0; i--)
                res.add(right.get(i));
            sum = leftSum + node.val + rightSum;
        }
        if (leftSum + node.val <= 0 && rightSum + node.val <= 0)
            return new ArrayList<Integer>();
        if (leftSum >= rightSum) {
            left.add(node.val);
            return left;
        } else {
            right.add(node.val);
            return right;
        }
    }
Read full article from 今�Hの国の呵呵君: [Algorithm]Get Path with Max Sum in Binary Tree