Leetcode#538把二叉搜索树转换为累加树
题目链接
刚开始看题的时候没有注意是二叉搜索树，所以只想到了用最傻x的方法：先将整个二叉树遍历一遍，取得所有val然后进行排序，再遍历二叉树分别，配合已经排序好的val数组进行循环累加。这样也是可以过的，但是不管时间复杂度还是空间复杂度都很高。
附一个不需要注释就能看懂的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public:
void dfs(TreeNode* node,vector<int>& nums)
{
nums.push_back(node -> val);
if(node -> left != nullptr)
dfs(node -> left,nums);
if(node -> right != nullptr)
dfs(node -> right,nums);
}
void dfs1(TreeNode* node,vector<int>& nums)
{
int sum = 0;
for(int i = 0 ; i < nums.size() ; i++)
{
if( nums[i] > node -> val)
sum+=nums[i];
}
node -> val += sum;
if(node -> left != nullptr)
dfs1(node -> left,nums);
if(node -> right != nullptr)
dfs1(node -> right,nums);
}
TreeNode* convertBST(TreeNode* root) {
vector<int>nums;
if(root == nullptr)
return nullptr;
dfs(root,nums);
sort(nums.begin(),nums.end());
dfs1(root,nums);
return root;
}
};
|
因为是二叉搜索树，所以已经排好了顺序，我们只需要通过反向中序遍历，就可以实现从大到小的累加和排序，只需要一遍就可以实现效果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int sum = 0;
TreeNode* convertBST(TreeNode* root) {
if (root != nullptr) {
convertBST(root->right);
sum += root->val;
root->val = sum;
convertBST(root->left);
}
return root;
}
};
|
