新手算法學習之路----二叉樹（二叉樹最大路徑和）

摘抄自：https://segmentfault.com/a/1190000003554858#articleHeader2

題目：

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.

思路：首先我們分析一下對于指定某個節點為根時，最大的路徑和有可能是哪些情況。第一種是左子樹的路徑加上當前節點，第二種是右子樹的路徑加上當前節點，第三種是左右子樹的路徑加上當前節點（相當于一條橫跨當前節點的路徑），第四種是只有自己的路徑。乍一看似乎以此為條件進行自下而上遞歸就行了，然而這四種情況只是用來計算以當前節點根的最大路徑，如果當前節點上面還有節點，那它的父節點是不能累加第三種情況的。所以我們要計算兩個最大值，一個是當前節點下最大路徑和，另一個是如果要連接父節點時最大的路徑和。我們用前者更新全局最大量，用后者返回遞歸值就行了。

Java代碼：

public class Solution {private int max = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {helper(root);return max;}public int helper(TreeNode root) {if(root == null) return 0;int left = helper(root.left);int right = helper(root.right);//連接父節點的最大路徑是一、二、四這三種情況的最大值int currSum = Math.max(Math.max(left + root.val, right + root.val), root.val);//當前節點的最大路徑是一、二、三、四這四種情況的最大值int currMax = Math.max(currSum, left + right + root.val);//用當前最大來更新全局最大max = Math.max(currMax, max);return currSum;}
}

?