題目：
Binary Tree Maximum Path Sum
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
|
1/ \2 3 |
Return 6.
節點可能為負數，尋找一條最路徑使得所經過節點和最大。路徑可以開始和結束于任何節點但是不能走回頭路。
這道題雖然看起來不同尋常，但是想一下，可以發現不外乎二叉樹的遍歷+簡單的動態規劃思想。
我們可以把問題拆分開：即便最后的最大路徑沒有經過根節點，它必然也有自己的“最高點”，因此我們只要針對所有結點，求出：如果路徑把這個節點作為“最高點”，路徑最長可達多少？記為max。然后在max中求出最大值MAX即為所求結果。和“求整數序列中的最大連續子序列”一樣思路。
下面就是找各個“最高點”對應的max之間的關系了。
我們拿根節點為例，對于經過根節點的最大路徑的計算方式為：
我們找出左子樹中以左孩子為起點的最大路徑長度a，和右子樹中以右孩子為起點的最大路徑長度b。然后這個點的max=MAX(a+b+node.val,a+node.val,b+node.val,node.val)
因此我們定義一個函數來算上面的a或者b，它的參數是一個節點，它的返回值是最大路徑長度，但是這個路徑的起點必須是輸入節點，而且路徑必須在以起點為根節點的子樹上。
那么函數func(node)的return值可以這樣定義：returnMAX(func(node.left)+node.val,func(node.right)+node.val,node.val)
終止條件是node==null，直接返回0。
接著我們發現上述計算max和求出MAX的過程完全可以放到func(node)里去。
按照這個思路的代碼，maxPathSumCore就是上面func(node)的實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution { public: int maxPathSum(TreeNode *root) { maxPathSumCore(root); return MAX; } int maxPathSumCore(TreeNode *node) { if(NULL == node) return 0; int a = maxPathSumCore(node -> left); int b = maxPathSumCore(node -> right); if((a+b+node->val) > MAX) MAX = (a+b+node->val); if((a+node->val) > MAX) MAX = (a+node->val); if((b+node->val) > MAX) MAX = (b+node->val); if(node->val > MAX) MAX = node->val; int maxViaThisNode = ((a + node->val) > node->val ? (a + node->val) : node->val); return (maxViaThisNode > (b + node->val) ? maxViaThisNode : (b + node->val)); } private: int MAX= -99999999;}; |
時間復雜度 O(n)，n為總節點數。
總結
以上就是本文關于java編程求二叉樹最大路徑問題代碼分析的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：https://www.cnblogs.com/felixfang/p/3637984.html
