C++ recursive explained to myself

• 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);
}
};
``````

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

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