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% 的用户