[recommend for beginners]clean C++ implementation with detailed explaination


  • 17

    Just use the "first" and "second" pointer to find the 2 nodes that violate the order. Then change the value of the first node ad the second node by their value.

    class Solution {
        TreeNode* first=NULL;
        TreeNode* second=NULL;
        TreeNode* prev = new TreeNode(INT_MIN);
    public:
        void recoverTree(TreeNode* root) {
            help(root);
            swp(first->val, second->val);
        }
        
        void help(TreeNode* root){
            if(root==NULL)  return;
            help(root->left);
            if(first==NULL && prev->val >= root->val)   first=prev;
            if(first!=NULL && prev->val >= root->val)   second=root;
            prev=root;
            help(root->right);
        }
    };

  • 3
    B

    I have a question... Is recursion considered as constant space?


  • 1
    S

    I have the same question, and I think the space complexity is O(log(n)) if recursion is used.


  • 0
    F
    class Solution {
        TreeNode* first = nullptr;
        TreeNode* second = nullptr;
        TreeNode* prev = new TreeNode(INT_MIN);
    public:
        void recoverTree(TreeNode* root) {
            help(root);
            swap(first->val, second->val);
        }
        
        void help(TreeNode* root) {
            if (!root) return;
            help(root->left);
            if (first == nullptr && prev->val >= root->val) first = prev;
            if (first != nullptr && prev->val >= root->val) second = root;
            prev = root;
            help(root->right);
        }
    };
    

Log in to reply
 

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