Leetcode538. 把二叉搜刮树转换为累加树(HOT100)
链接我的正确代码：
class Solution {
public:
int curSum = 0;
TreeNode* convertBST(TreeNode* root) {
if (!root)
return nullptr;
order(root);
return root;
}
void order(TreeNode* root) {
if (!root)
return;
order(root->right);
curSum += root->val;
root->val = curSum;
order(root->left);
}
}; 首先：
对于一个递增数组而言，要将每个元素置为大于等于它的元素之和，那么我们从右往左遍历，维护后缀和即可。
而对于二叉搜刮树，有一个性质：中序遍历是递增的，那么反向中序遍历就是递减的。
以是我们反向中序遍历即可。
代码：
class Solution {
public:
int curSum = 0;
TreeNode* convertBST(TreeNode* root) {
dfs(root);
return root;
}
void dfs(TreeNode* root){
if(!root)
return;
dfs(root->right);
curSum+=root->val;
root->val = curSum;
dfs(root->left);
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]