首页 > 代码库 > [Leetcode][Tree][Binary Tree Maximum Path Sum]

[Leetcode][Tree][Binary Tree Maximum Path Sum]

2024-07-10 21:45:48   225人阅读

找书中权值和最大的路径，至少包含一个点。

有点类似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。


联系
我们