Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum II

Description: Given a binary tree, find the maximum path sum from the root. The path may start and end at any node in the tree and contains at least one node.

Analysis: Since the path starts from root and ends at any node, we just need to compare (root.value), (root.value+left Max Path Sum) and (root.value+right Max Path Sum).

public int maxPathSum(TreeNode root) {

        if (root == null)
            return 0;
        if (root.left == null && root.right == null)
            return root.val;

        return Math.max(root.val, 
                        root.val+maxPathSum(root.left), 
                        root.val+maxPathSum(root.right));
    }

Binary Tree Maximum Path Sum

Analysis: Find the maximum path sum from any node to any node. There are three situations when finding a Maximum Path Sum:

1. A path only inside left subtree

2. A path only inside right subtree

3. A path across the root, containing nodes of left and right subtrees.

class ResultType {
    public int root2Any, any2Any;
    public ResultType (int root2Any, int any2Any) {
        this.root2Any = root2Any;
        this.any2Any = any2Any;
    }
}

public class Solution {

    private ResultType Helper (TreeNode root){
        if (root == null)
            return new ResultType(0, Integer.MIN_VALUE);

        ResultType left = Helper(root.left);
        ResultType right = Helper(root.right);

        int root2Any = Math.max(root.val+left.root2Any, root.val+right.root2Any);
        root2Any = Math.max(0, root2Any);
        int any2Any = Math.max(left.any2Any, right.any2Any); 
        any2Any = Math.max(any2Any, left.root2Any+root.val+right.root2Any);
        return new ResultType(root2Any, any2Any);
    }

    public int maxPathSum(TreeNode root) {
        ResultType result = Helper(root);
        return result.any2Any;
    }
}