Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]Binary Tree Maximum Path Sum-2014.01.19

Posted on 2014-01-19 21:48 Uriel 阅读(177) 评论(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 };

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理