C++ recursive explained to myself


  • 0
    Y

    Looked around and felt none of folks really explained why recursive works, so I'll explain to myself.

    class Solution {
    public:
        void recoverTree(TreeNode* root) {
            TreeNode* pre=NULL;
            TreeNode* p1=NULL;
            TreeNode* p2=NULL;
            visit(root, pre, p1 ,p2);
            if(p1 && p2 ){
                int temp  = p1->val;
                p1->val =p2->val;
                p2->val = temp;
            }
        }
        
        void visit(TreeNode* root, TreeNode*& pre, TreeNode*& p1, TreeNode*& p2){
            if(!root)
                return;
            if(root->left)
                visit(root->left , pre, p1, p2 );
            if(pre && pre->val >= root->val){
                if(!p1){      
    // so this is the first time when you see a node's val is no less than its left immediate child
    // you need to store, since these two may possibly be the two nodes to swap.
                    p1=pre;
                    p2=root;
                }
                else
                    p2=root;   // so turns out there is second node with violation that has nothing to do with first one ( not directly linked).
            }
            pre =root;
            visit(root->right, pre, p1 ,p2);
        }
    };
    

  • 0

    it seems that recursion uses O(n) space ...


Log in to reply
 

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