二、解题思路
- 二叉搜索树的中序遍历是递增序列
- 我们可以首先中序遍历二叉搜索树,将数字存入
vector
- 新树的值为从
vector
末尾开始,为从末尾元素到当前的元素sum
- 二叉搜索树的反中序遍历是递减序列
三、解题代码
class Solution {
public:
TreeNode* bstToGst(TreeNode* root) {
if(!root) return root;
vector<int> vec;
stack<TreeNode*>s;
auto p = root;
while(!s.empty() || p){
while(p){
s.push(p);
p = p->left;
}
if(!s.empty()){
p = s.top();
s.pop();
vec.push_back(p->val);
p = p->right;
}
}
int sum = 0;
for(auto i = vec.rbegin(); i != vec.rend(); i++){
sum += *i;
*i = sum;
}
int counter = 0;
p = root;
while(!s.empty() || p){
while(p){
s.push(p);
p = p->left;
}
if(!s.empty()){
p = s.top();
s.pop();
p->val = vec[counter++];
p = p->right;
}
}
return root;
}
};
class Solution {
public:
int sum = 0;
public:
TreeNode* bstToGst(TreeNode* root) {
if(root){
root->right = bstToGst(root->right);
sum += root->val;
root->val = sum;
root->left = bstToGst(root->left);
}
return root;
}
};
四、运行结果