【題目】
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.
【分析】
需要考慮以上兩種情況：
1 左子樹或者右子樹中存有最大路徑和 不能和根節點形成一個路徑<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+MiDX89fTyvcg09LX08r3ILrNuPm92rXj0M6zydfutPPCt762PC9wPgo8aDQ+ob60+sLrob88L2g0Pgo8cD48L3A+CjxwcmUgY2xhc3M9"brush:java;">/*********************************
* 日期：2014-12-23
* 作者：SJF0115
* 題號: Binary Tree Maximum Path Sum
* 來源：https://oj.leetcode.com/problems/binary-tree-maximum-path-sum/
* 結果：AC
* 來源：LeetCode
* 總結：
**********************************/
#include
#include
#include
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxPathSum(TreeNode *root) {
if(root == NULL){
return 0;
}//if
maxSum = INT_MIN;
maxPath(root);
return maxSum;
}
private:
int maxSum;
int maxPath(TreeNode *node){
if(node == NULL){
return 0;
}//if
// 左子樹最大路徑值(路徑特點：左右節點只能選一個)
int leftMax = maxPath(node->left);
// 右子樹最大路徑值(路徑特點：左右節點只能選一個)
int rightMax = maxPath(node->right);
// 以node節點的雙側路徑((node節點以及左右子樹))
int curMax = node->val;
if(leftMax > 0){
curMax += leftMax;
}//if
if(rightMax > 0){
curMax += rightMax;
}//if
maxSum = max(curMax,maxSum);
// 以node節點的單側路徑(node節點以及左右子樹的一個)
if(max(leftMax,rightMax) > 0){
return max(leftMax,rightMax) + node->val;
}
else{
return node->val;
}
}
};
//按先序序列創建二叉樹
int CreateBTree(TreeNode*& T){
int data;
//按先序次序輸入二叉樹中結點的值,-1表示空樹
cin>>data;
if(data == -1){
T = NULL;
}
else{
T = (TreeNode*)malloc(sizeof(TreeNode));
//生成根結點
T->val = data;
//構造左子樹
CreateBTree(T->left);
//構造右子樹
CreateBTree(T->right);
}
return 0;
}
int main() {
Solution solution;
TreeNode* root(0);
CreateBTree(root);
cout<
