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.

Example

Given the below binary tree:

  1
 / \
2   3

return 6.

Solution: Divide and Conquer. for each node, calculate two maxPath:

1. maxSinglePath: start from root to any nodes, could be empty. 从root往下走到任意点的最大路径,这条路径可以不包含任何点.

2. maxPath: 从树中任意到任意点的最大路径,这条路径至少包含一个点. Max path in the tree, can not be empty, doesn’t have to include root.

So the result is root.maxPath

O(n) time complexity. Each node is visited once.

Version 1. cleaner version, with global variable

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
     
    int maxPath = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        maxSinglePath(root);
        return maxPath;
    }
    
    public int maxSinglePath(TreeNode root){
        if(root==null){
            return 0;
        }
        //devide
        int left = Math.max(0, maxSinglePath(root.left));
        int right = Math.max(0, maxSinglePath(root.right));
        
        //conquer
        maxPath = Math.max(maxPath, left+right+root.val);
        
        return Math.max(left, right)+root.val;
    }
}

Version 2. jiuzhang, with result class

private class maxPathResult {
    int maxSinglePath;
    int maxPath;
    public maxPathResult(int maxSinglePath, int maxPath) {
        this.maxSinglePath = maxSinglePath;//start from root to any nodes, could be empty
        this.maxPath = maxPath;//max path in the tree, can not be empty, doesn't have to include root
    }
}
public int maxPathSum(TreeNode root) {
    // write your code here
    return helper(root).maxPath;
}

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

    //conquer
    int maxSinglePath = Math.max(left.maxSinglePath, right.maxSinglePath) + root.val;
    maxSinglePath = Math.max(maxSinglePath, 0);

    int maxDoublePath = left.maxSinglePath + right.maxSinglePath + root.val;

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

 

FacebookTwitterGoogle+Share