Leetcode538. 把二叉搜刮树转换为累加树(HOT100)

链接
我的正确代码：

1. class Solution {
2. public:
3.     int curSum = 0;
4.     TreeNode* convertBST(TreeNode* root) {
5.         if (!root)
6.             return nullptr;
7.         order(root);
8.         return root;
9.     }
10.     void order(TreeNode* root) {
11.         if (!root)
12.             return;
13.         order(root->right);
14.         curSum += root->val;
15.         root->val = curSum;
16.         order(root->left);
17.     }
18. };

复制代码

首先：
对于一个递增数组而言，要将每个元素置为大于等于它的元素之和，那么我们从右往左遍历，维护后缀和即可。
而对于二叉搜刮树，有一个性质：中序遍历是递增的，那么反向中序遍历就是递减的。
以是我们反向中序遍历即可。
代码：
 

1. class Solution {
2. public:
3.     int curSum = 0;
5.     TreeNode* convertBST(TreeNode* root) {
6.         dfs(root);
7.         return root;
8.     }
9.     void dfs(TreeNode* root){
10.         if(!root)
11.             return;
12.         dfs(root->right);
13.         curSum+=root->val;
14.         root->val = curSum;
15.         dfs(root->left);
16.     }
17. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。