tag:
- Hard;
- Depth-first Search;
question:
??Given a non-empty 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.
Example 1:
Input: [1,2,3]
??? 1
??? / \
???2 3
Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7]
??? -10
??? / \
???9 20
????/ \
???15 7
Output: 42
思路：
??首先我們分析一下對于指定某個節(jié)點為根時脉幢，最大的路徑和有可能是哪些情況:
- 最大路徑包含該根節(jié)點：
最大路徑之和=根節(jié)點的值+深度遍歷其左子樹的路徑和的最大值 +深度遍歷其右子樹的路徑和的最大值 - 最大路徑不包含該根節(jié)點：
①該根節(jié)點的左孩子作為新的根節(jié)點的最大路徑和
②該根節(jié)點的右孩子作為新的根節(jié)點的最大路徑和
最大路徑和為三者中的最大值歪沃。
??在遞歸函數(shù)中，如果當前結(jié)點不存在鸵隧，那么直接返回0绸罗。否則就分別對其左右子節(jié)點調(diào)用遞歸函數(shù)，由于路徑和有可能為負數(shù)豆瘫，而我們當然不希望加上負的路徑和珊蟀，所以我們和0相比，取較大的那個外驱，就是要么不加育灸，加就要加正數(shù)。然后我們來更新全局最大值結(jié)果res昵宇，就是以左子結(jié)點為終點的最大path之和加上以右子結(jié)點為終點的最大path之和磅崭，還要加上當前結(jié)點值，這樣就組成了一個條完整的路徑瓦哎。而我們返回值是取left和right中的較大值加上當前結(jié)點值砸喻，因為我們返回值的定義是以當前結(jié)點為終點的path之和，所以只能取left和right中較大的那個值蒋譬，而不是兩個都要割岛，參見代碼如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode* root) {
int res = INT_MIN;
helper(root, res);
return res;
}
int helper(TreeNode* root, int &res) {
if (!root)
return 0;
int left = max(helper(root->left, res), 0);
int right = max(helper(root->right, res), 0);
res = max(res, left + right + root->val);
return max(left, right) + root->val;
}
};
