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,1 / 2 3
Return
6.
算法思路：
应该先计算出root节点左、右子树中的最长路径left, right，然后经过root节点的最长路径应该是root.val ,root.val + left, root.val + right, root.val + left + right中的最大者。
因为计算root节点时，需要先求出left 和right子节点，因此本题该采取后序遍历。
代码如下：
1 public class Solution { 2 int max = Integer.MIN_VALUE; 3 public int maxPathSum(TreeNode root) { 4 if(root == null) return 0; 5 dfs(root); 6 return max; 7 } 8 private int dfs(TreeNode root){ 9 if(root == null) return 0; 10 int left = dfs(root.left); 11 int right = dfs(root.right); 12 max = Math.max(max,Math.max(root.val,Math.max(root.val + left + right,Math.max(root.val + left,root.val + right)))); 13 return Math.max(root.val , Math.max(root.val + left,root.val + right)); 14 } 15 }
实在还是不明白的，可以看这里。
[leetcode]Binary Tree Maximum Path Sum,布布扣,bubuko.com
[leetcode]Binary Tree Maximum Path Sum
原文：http://www.cnblogs.com/huntfor/p/3905489.html