首页 > 代码库 > [Leetcode][Tree][Binary Tree Maximum Path Sum]
[Leetcode][Tree][Binary Tree Maximum Path Sum]
找书中权值和最大的路径,至少包含一个点。
有点类似LCA(最近公共祖先),树的问题关键是如何划分子问题,然后递归求解。
想到了可以返回两种结果,一个是单独路径的最大和,一种是子树的最大和,然后在求解的过程中不断的更新答案。
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 //first is the maximum path sum13 //second is the maximum subtree sum14 //path and subtree should contain at least one node15 pair<int, int> findRes(TreeNode * root, int & res) {16 pair<int, int> values = make_pair(INT_MIN, INT_MIN);17 if (root == NULL) {18 return values;19 }20 pair<int, int> lvalues = findRes(root->left, res);21 pair<int, int> rvalues = findRes(root->right, res);22 values.first = max(0, max(lvalues.first, rvalues.first)) + root->val;23 24 values.second = max(lvalues.second, rvalues.second);25 int sum = root->val;26 if (lvalues.first > 0) {27 sum += lvalues.first;28 }29 if (rvalues.first > 0) {30 sum += rvalues.first;31 }32 values.second = max(values.second, sum);33 res = max(res, values.second);34 res = max(res, values.first);35 return values;36 }37 int maxPathSum(TreeNode *root) {38 int res = INT_MIN;39 findRes(root, res);40 return res;41 }42 };
总结:CE了两次。。总是不小心打错单词。。哭。。。
WA了一次,其实当时想到了,如果树中的结点权值均为负数的时候,不应该把res初始化为0。
看了题解之后,恍然大悟,子树的值是不需要被返回的!于是又重写了一遍,争取把代码写的更简洁!
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 //findRes returns the maximum path sum ended with root.13 int findRes(TreeNode *root, int & res) {14 if (root == NULL) {15 return 0;16 }17 int l = findRes(root->left, res);18 int r = findRes(root->right, res);19 int sum = root->val;20 if (l > 0) {21 sum += l;22 }23 if (r > 0) {24 sum += r;25 }26 res = max(res, sum);//update the final result27 if (l <= 0 && r <= 0) {28 return root->val;29 } else {30 return max(l, r) + root->val;31 }32 }33 int maxPathSum(TreeNode *root) {34 int res = INT_MIN;35 findRes(root, res);36 return res;37 }38 };
一次AC。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。