538. 把二叉搜索树转换为累加树

朴灿烈づ我的快乐病毒、 2021-12-24 00:34 269阅读 0赞

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

输入: 二叉搜索树:  
5  
/ \\  
2 13

输出: 转换为累加树:  
18  
/ \\  
20 13

思路:我原先思考的时候是前序遍历，即根左右，但是没有估计到所有的情况，所以通过了一部分，后来一看解析递归右根左，或者用栈模拟即可。

附上第一次傻逼的代码：

/**
     * 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 {
    public:
        TreeNode* convertBST(TreeNode* root) {
            if(root==NULL)
                return NULL;
        
              reRes(root,0,0);
            return root;
        }
        
        void  reRes(TreeNode* root,int last,int cur){
            
            if(root==NULL)
                return;
            int now = root->val;
            int l = last;
            int r = rsum(root->right);
            if(cur>root->val){
                
                root->val  = root->val+l+r;
            }else{
                
                root->val = root->val+r;
            }
            reRes(root->left,root->val,now);
            reRes(root->right,root->val,now);
        
        }
        int rsum(TreeNode* root){
            
            if(root==NULL)
            return 0;
            
            return root->val+rsum(root->left)+rsum(root->right);    
        }
        
    };

正确的做法：  
即右根左即可

非递归写法：

/**
     * 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 {
    public:
        
        int pre = 0;
        TreeNode* convertBST(TreeNode* root) {
            
            if(root==NULL)
                return root;
            
            stack<TreeNode*> stack;
            TreeNode * node = root;
            while(node!= NULL || !stack.empty()){
                if(node!=NULL)
                {
                    stack.push(node);
                    node = node->right;
                }else{
                    
                    node = stack.top();
                    stack.pop();
                    node->val += pre;
                    pre = node->val;
                    
                    node = node->left;
                }
                
                
            }
            return root;
        }
    };