Posted on 2014-01-19 21:48
Uriel 阅读(170)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
二叉树，每个节点有一个权值，求二叉树上权值和最大的一条路，返回权值和
本来看题目以为是树形DP什么的，结果又是DFS。。没考虑负数情况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 };