538.Convert BST to Greater Tree
538.Convert BST to Greater Tree
难度:Easy
给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如:
1
输入: 二叉搜索树:
2
5
3
/ \
4
2 13
5
6
输出: 转换为累加树:
7
18
8
/ \
9
20 13
Copied!
需要将二叉树从小到大排列,然后逐个相加,由于是BST,因此中序遍历即可。
1
/**
2
* Definition for a binary tree node.
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
private:
12
stack<TreeNode*> all;
13
void traversal(TreeNode* root)
14
{
15
if(!root) return;
16
if(root->left) traversal(root->left);
17
all.push(root);
18
if(root->right) traversal(root->right);
19
}
20
public:
21
TreeNode* convertBST(TreeNode* root) {
22
if(!root) return 0;
23
traversal(root);
24
int s=0;
25
//cout<<all.size()<<endl;
26
while(!all.empty())
27
{
28
s+=all.top()->val;
29
// cout<<s<<endl;
30
all.top()->val=s;
31
all.pop();
32
}
33
34
35
return root;
36
}
37
};
Copied!
执行用时 : 56 ms, 在Convert BST to Greater Tree的C++提交中击败了91.81% 的用户 内存消耗 : 24.2 MB, 在Convert BST to Greater Tree的C++提交中击败了79.10% 的用户
Copy link