Leetcode-124: Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:

Given the below binary tree,

1
      / \
     2   3
      

Return 

6

.

求給定的一顆二叉樹中，從某個葉節點到另一個葉節點之間的最大路徑和，這條路徑不一定需要經過根節點。

思路：二叉樹中如果一條路徑要連接配接兩個葉節點，那麼這條路徑一定經過兩個葉節點的共同祖先節點A，而且路徑的一部分是A經過A的左子節點A.left到葉節點的路徑，另一部分是A經過A的右子節點A.right到另一個葉節點的路徑。那麼該題可以重新描述為：找到樹種的一個節點A，使得A.left到葉節點的最大路徑和、A.right到葉節點的最大路徑和與A.val三者之和最大。可以看到周遊順序是left->right->root，此時需要用後序周遊（postorder traversal）。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int maxValue = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        if (root == null)
            return 0;
        postorder(root);
        return maxValue;
    }
    
    private int postorder(TreeNode h) {
        if (h == null)
            return 0;
        
        int left = Math.max(0, postorder(h.left));
        int right = Math.max(0, postorder(h.right));
        maxValue = Math.max(maxValue, left + right + h.val);
        return Math.max(left, right) + h.val;
    }
}