My 32 ms C++ iterative inorder traversal


  • 0
    V
    class Solution {
    public:
        void recoverTree(TreeNode* root) {
            TreeNode *curr = NULL;
            TreeNode *prev = NULL;
            stack<TreeNode *> s;
            TreeNode *swapNode = NULL;
            curr = root;
            while(curr != NULL  || !s.empty()) {
                if(curr != NULL) {
                    s.push(curr);
                    curr = curr->left;
                    continue;
                }
                curr = s.top();
                s.pop();
                if(prev == NULL || prev->val < curr->val) {
                    prev = curr;
                    curr = curr->right;
                    continue;
                }
                if(findNodeLesser(curr->right, s, curr->val, &swapNode) == true) {
                    fSwap(prev, swapNode);
                } else {
                    fSwap(prev, curr);
                }
                break;
            }
        }
        
        void fSwap(TreeNode *a, TreeNode *b) {
            int temp = a->val;
            a->val = b->val;
            b->val = temp;
        }
        
        bool findNodeLesser(TreeNode *n, stack<TreeNode *> &s, int target, TreeNode **swapNode) {
            TreeNode *curr = n;
            while(curr != NULL  || !s.empty()) {
                if(curr != NULL) {
                    s.push(curr);
                    curr = curr->left;
                    continue;
                }
                curr = s.top();
                s.pop();
                if(curr->val < target) {
                    *swapNode = curr;
                    return true;
                }
                curr = curr->right;
            }
            return false;
        }
    };
    

Log in to reply
 

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