Lexi's Leetcode solutions

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

Posted on: November 4, 2013


  • arch代表穿过当前节点的路径(左边一支儿+自己节点+右边一支儿)。
  • 注意树的节点可以是负数,所以arch不一定是最长的。
  • 每次return以root(当前节点)开头最大的单只path sum。
  • res[]就是一个存result的reference object,java不支持c++那种直接&传reference,
  • 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: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: