[538. Convert BST to Greater Tree] Inorder Using stack or recursive method _C++


  • 0
    class Solution {
    public:
    TreeNode* convertBST(TreeNode* root) {
        if(root == nullptr) return root;
        int sum = 0;
        dfs(root, sum);
        return root;
     }
    
     void dfs(TreeNode* root, int& sum){
        if(root == nullptr) return;
        dfs(root->right, sum);
        sum += root->val;
        root->val = sum;
        dfs(root->left, sum);
    }
    };
    

    class Solution {
     public:
    TreeNode* convertBST(TreeNode* root) {
        if(root == nullptr) return root;
        auto root2 = root;
        vector<TreeNode*> vec;
        stack<TreeNode*> sk;
        int sum = 0;
        while(true){
            while(root){
                sk.push(root);
                root = root->left;
            }
            if(sk.empty()) break;
            auto tmp = sk.top();
            sum += tmp->val;
            sk.pop();
            vec.push_back(tmp);
            root = tmp->right;
        }
        for(auto node : vec){
            sum -= node->val;
            node->val += sum;
        }
        return root2;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.