# My non-recursive solution with the help of a stack

• Here is my solution, its time complex is O(n), and since it is non-recursive, the space complex maybe optimal than those recursive versions.

`````` /**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void recoverTree(TreeNode *root) {
if(root == NULL){
return;
}
stack<TreeNode *> nodeStack;
TreeNode *pre = NULL;
TreeNode *apre = NULL;
TreeNode *apro = NULL;
TreeNode *bpre = NULL;
TreeNode *bpro = NULL;
TreeNode *cur = root;
while(cur != NULL || !nodeStack.empty()){
while(cur != NULL){
nodeStack.push(cur);
cur = cur->left;
}
if(!nodeStack.empty()){
cur = nodeStack.top();
nodeStack.pop();
//process
if(pre == NULL){
pre = cur;
}else{
if(cur->val < pre->val){
if(apre == NULL){
apre = pre;
apro = cur;
}else{
bpre = pre;
bpro = cur;
}
}
pre = cur;
}
cur = cur->right;
}
}
if(bpre == NULL){
int temp = apre->val;
apre->val = apro->val;
apro->val = temp;
}else{
int temp = apre->val;
apre->val = bpro->val;
bpro->val = temp;
}
}
};``````

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