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;
    }
}