I am using common inorder-traversal both in iteration and recursion.

but, iteration version got 56ms, and recursion version got 48ms.

did anyone know the reason?

Here goes the code:

**Iteration**:

```
class Solution {
public:
void recoverTree(TreeNode* root) {
if(!root) return;
TreeNode * cur = root, * pre = nullptr, *first = nullptr, * second = nullptr;
stack<TreeNode*> stk;
while(cur||!stk.empty()){
while(cur){
stk.push(cur);
cur = cur->left;
}
cur = stk.top();
stk.pop();
if(pre && cur->val < pre->val){
if(!first) {
first = pre;
second = cur;
}
else{
second = cur;
swap(first, second);
return;
}
}
pre = cur;
cur = cur->right;
}
swap(first, second);
}
void swap(TreeNode* first, TreeNode* second){
if(!first || !second) return;
int tmp = first->val;
first->val = second->val;
second->val = tmp;
}
};
```

**Recursion**:

```
class Solution {
private:
public:
void recoverTree(TreeNode* root) {
TreeNode * pre = nullptr, * first = nullptr, * second = nullptr;
traversal(root, pre, first, second);
swap(first, second);
}
void traversal(TreeNode * root, TreeNode * & pre, TreeNode * &first, TreeNode * &second){
if(!root) return;
traversal(root->left, pre, first, second);
if(pre && root->val < pre->val){
if(!first){
first = pre;
second = root;
}else second = root;
}
pre = root;
traversal(root->right, pre, first, second);
}
void swap(TreeNode* first, TreeNode* second){
if(!first || !second) return;
int tmp = first->val;
first->val = second->val;
second->val = tmp;
}
};
```