538.Convert BST to Greater Tree
538.Convert BST to Greater Tree
难度:Easy
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如：
输入: 二叉搜索树:
5
/ \
2 13
输出: 转换为累加树:
18
/ \
20 13
需要将二叉树从小到大排列，然后逐个相加，由于是BST，因此中序遍历即可。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
stack<TreeNode*> all;
void traversal(TreeNode* root)
{
if(!root) return;
if(root->left) traversal(root->left);
all.push(root);
if(root->right) traversal(root->right);
}
public:
TreeNode* convertBST(TreeNode* root) {
if(!root) return 0;
traversal(root);
int s=0;
//cout<<all.size()<<endl;
while(!all.empty())
{
s+=all.top()->val;
// cout<<s<<endl;
all.top()->val=s;
all.pop();
}
return root;
}
};
执行用时 : 56 ms, 在Convert BST to Greater Tree的C++提交中击败了91.81% 的用户 内存消耗 : 24.2 MB, 在Convert BST to Greater Tree的C++提交中击败了79.10% 的用户
Last modified 11mo ago