Binary Tree Maximum Path Sum, Leetcode 解题笔记

Given a binary tree, find the maximum path sum.

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

For example:
Given the below binary tree,

1
/ \
2 3
Return 6.

看了网上几个讲解,感觉下面这个是最清晰的:
http://www.cnblogs.com/lautsie/p/3249723.html
基本的思路就是,在递归中计算包含该root的最大值并更新至max[0](Java无法按引用传,就只能建立一个数组或用wrapper class或用全局变量)。

包含该root的最大值有如下几种可能:1.root本身;2.root和左子树中一条路径;3.root和右子树中一条路径;4.左子树一条路径和root和右子树一条路径。其中取最大就可更新至max[0]

其中1,2,3可用来计算上一级的root的最大值,所以要传回去。

最终,对于最上层的root来说,数内的最大路径不一定要经过根,但由于每个节点都遍历到,其最大值已经存在max[0]里面了。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxPathSum(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int max[] = new int[1]; // this is used to keep max val
        max[0] = Integer.MIN_VALUE;
        localSum(root, max);
        return max[0];       
    }
     
    public int localSum(TreeNode root, int[] max) {
        if (root == null) return 0;
        int lsum = localSum(root.left, max);
        int rsum = localSum(root.right, max);
        int csum = Math.max(root.val, Math.max(root.val + lsum, root.val + rsum));
         
        max[0] = Math.max(max[0], Math.max(csum, lsum + root.val + rsum));
        return csum;
    }     
}

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s