Wednesday, March 20, 2013

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,

      / \
     2   3
Return 6.

recursive function, returns the maximum single sided sum, and updates the maximum double sided sum while doing the recursion.

public class Solution {
    int findMaxSingleSide(TreeNode root, int[] max){
        if(root == null) {
            return 0;
        int left = findMaxSingleSide(root.left,max);
        int right = findMaxSingleSide(root.right,max);
        int longer = Math.max(left,right);
        int result = Math.max(root.val, root.val+longer);
        int newMax = root.val;
        newMax = Math.max(newMax, newMax + left);
        newMax = Math.max(newMax, newMax + right);
        max[0] = Math.max(max[0], newMax);
        return result;
    public int maxPathSum(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(root == null) return 0;
        int[] ret = new int[1];
        ret[0] = root.val;
        findMaxSingleSide(root, ret);
        return ret[0];

No comments:

Post a Comment

Manacher's Longest Palindromic Substring Algorithm