Posted on 2014-01-19 21:48
Uriel 閱讀(208)
評論(0) 編輯 收藏 引用 所屬分類:
LeetCode
二叉樹，每個節(jié)點有一個權(quán)值，求二叉樹上權(quán)值和最大的一條路，返回權(quán)值和
本來看題目以為是樹形DP什么的，結(jié)果又是DFS。。沒考慮負數(shù)情況WA一次。。
1 /**
2 * Definition for binary tree
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 int res;
13
14 int DFS(TreeNode *root, int sum) {
15 if(root == NULL) return INT_MIN;
16 int suml = DFS(root->left, sum);
17 int sumr = DFS(root->right, sum);
18 int tp = root->val;
19 if(suml > 0) tp += suml;
20 if(sumr > 0) tp += sumr;
21 res = max(tp, res);
22 return max(max(suml, sumr), 0) + root->val;
23 }
24
25 int maxPathSum(TreeNode *root) {
26 if(root == NULL) return 0;
27 res = root->val;
28 DFS(root, root->val);
29 return res;
30 }
31 };