3.3 Binary Tree Maximum Path Sum II

Given a binary tree, find the maximum path sum from root.

The path may end at any node in the tree and contain at least one node in it.

Code Template: recursive

public int maxPathSum2(TreeNode root) {
    return helper(root, 0);
}

public int helper(TreeNode root, int pathSum) {
    // base case: if already at null, return path sum
    if (root == null)
        return pathSum;

    // add current level val into path sum    
    pathSum += root.val;    

    // divide: calculate path sum of left and right tree
    int left = helper(root.left, pathSum);
    int right = helper(root.right, pathSum);

    // pick the max from left and right tree
    return Math.max(left, right);
}