[leetcode] Binary Tree Maximum Path Sum |树中任意两点间最大path sum

Posted by: lexigrey on: November 4, 2013

• In: leetcode
• 1 Comment

算法：

• arch代表穿过当前节点的路径（左边一支儿+自己节点+右边一支儿）。
• 注意树的节点可以是负数，所以arch不一定是最长的。
• 每次return以root（当前节点）开头最大的单只path sum。
• res[]就是一个存result的reference object，java不支持c++那种直接&传reference，
  所以要么用个长度为一的数组，要么写个wrapper。还是用数组简单。
• update res[0]，用arch和以自己开头一支儿的比，谁大就把res[0] update成谁。

public int maxPathSum(TreeNode root) {
    int[] res = new int[1];
    res[0] = Integer.MIN_VALUE;
    maxPath(root, res);
    return res[0];
}
private int maxPath(TreeNode root, int[] res) {
    if (root == null)
        return 0;
    int left = maxPath(root.left, res);//左边一支儿（不算自己）
    int right = maxPath(root.right, res);
    int arch = left + right + root.val; //穿过自己
    int single = Math.max(root.val, Math.max(left, right) + root.val);
    //（算上自己）
    res[0] = Math.max(res[0], Math.max(arch, single));//update结果
    return single;
}

Tags: tree, 后序