Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

<code>  1
 / \
2   3
</code>

private class maxPathResult {
    int maxSinglePath;
    int maxPath;
    public maxPathResult(int maxSinglePath, int maxPath) {
        this.maxSinglePath = maxSinglePath;//start from root to any nodes
        this.maxPath = maxPath;//max path in the tree
    }
}
public int maxPathSum(TreeNode root) {
    // write your code here
    return helper(root).maxPath;
}

public maxPathResult helper(TreeNode root) {
    if (root == null) {
        return new maxPathResult(Integer.MIN_VALUE, Integer.MIN_VALUE);
    }
    maxPathResult left = helper(root.left);
    maxPathResult right = helper(root.right);

    int maxSinglePath = Math.max(left.maxSinglePath, right.maxSinglePath);
    maxSinglePath = maxSinglePath < 0 ? root.val : root.val + maxSinglePath;

    int maxDoublePath = 0;
    if (left.maxSinglePath > 0) {
        maxDoublePath += left.maxSinglePath;
    }
    if (right.maxSinglePath > 0) {
        maxDoublePath += right.maxSinglePath;
    }
    maxDoublePath += root.val;

    int maxPath = Math.max(Math.max(left.maxPath, right.maxPath), maxDoublePath);
    return new maxPathResult(maxSinglePath, maxPath);
}

计算树的最长path有2种情况：

1. 通过根的path.

(1)如果左子树从左树根到任何一个Node的path大于零，可以链到root上

(2)如果右子树从右树根到任何一个Node的path大于零，可以链到root上

2. 不通过根的path. 这个可以取左子树及右子树的path的最大值。

所以创建一个inner class:

记录2个值：

1. 本树的最大path。

2. 本树从根节点出发到任何一个节点的最大path.

注意，当root == null,以上2个值都要置为Integer_MIN_VALUE; 因为没有节点可取的时候，是不存在solution的。以免干扰递归的计算

九章详解

Share