Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

 

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.


Naive Way: 可以用一个recursive的方法，不断比较sum(root.left), sum(root.right)和root.val，在回溯过程中遇到正数也要和最大值比较。

 

Recursive的方法，算法复杂度O(n), space O(n)。这里因为Integer.MIN_VALUE+负数 =正数,所以不能直接写return max(root.val, root.val+right, root.val+left)，必须确认left.val和right.val都是正数。

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        int rootSum = pSum(root);
        return Math.max(rootSum,max);
    }
    
    private int pSum(TreeNode root) {
        // base case
        if(root==null){return Integer.MIN_VALUE;}
        // recursive
        int left = pSum(root.left);
        int right = pSum(root.right);
        max = Math.max(left,max);
        max = Math.max(right,max);
        if(left < 0 && right < 0)
            return root.val;
        else if(left < 0)
            return root.val+right;
        else if(right < 0)
            return root.val+left;
        else
            max = Math.max(root.val+left+right,max);
        return root.val + Math.max(right,left);
    }
    
}

下面是iterative的方法。使用了level-order traversal，相当于BFS，正着一遍将所有节点放入对应的层中，然后倒着一遍由下往上求一遍。还可以用DFS遍历一遍然后全存入一个堆栈中，遍历完后再逐个推出堆栈，因为其顺序也是倒着的（相当于拓扑排序的顺序）。

public class Solution {
    public int maxPathSum(TreeNode root) {
        // level-order traversal
        List<List<TreeNode>> gross = new ArrayList<List<TreeNode>>();
        int max = Integer.MIN_VALUE;
        // initialize
        List<TreeNode> first_layer = new ArrayList<TreeNode>();
        if(root!=null) first_layer.add(root);
        gross.add(first_layer);
        while(gross.get(gross.size()-1).size() > 0){
            List<TreeNode> new_layer = new ArrayList<TreeNode>();
            List<TreeNode> pre_layer = gross.get(gross.size()-1);
            for(int i = 0;i < pre_layer.size();i++){
                TreeNode node = pre_layer.get(i);
                if(node.left!=null) new_layer.add(node.left);
                if(node.right!=null) new_layer.add(node.right);
            }
            gross.add(new_layer);
        }
        
        // back trace
        int index = gross.size();
        while(--index >= 0){
            List<TreeNode> last_layer = gross.get(index);
            for(int i = 0;i < last_layer.size();i++){
                TreeNode node = last_layer.get(i);
                if(node.right!=null && node.left==null){
                    node.val += node.right.val>0?node.right.val:0;
                }else if(node.left!=null && node.right==null){
                    node.val += node.left.val>0?node.left.val:0;
                }else if(node.left!=null && node.right!=null){
                    max = Math.max(max, node.val+node.left.val+node.right.val);
                    node.val += Math.max(Math.max(node.left.val,node.right.val),0);
                }
                max = Math.max(max,node.val);
            }
        }
        
        return max;
    }
}