My non-recursive solution with the help of a stack


  • 1
    L

    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;
                }
            }
        };

Log in to reply
 

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