O(1) space, iterativeInorder traversal C++


  • -1
    H

    class Solution {
    public:
    void recoverTree(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> stk;
    TreeNode* P1;
    TreeNode* P2;
    bool flag1 = false;
    bool flag2 = false;
    int lastNodeVal = INT_MIN;
    TreeNode* lastP;
    int NodeVal1;
    int NodeVal2;
    TreeNode* peakNode = NULL;
    while(!stk.empty() || root != NULL)
    {
    if(root != NULL)
    {
    stk.push(root);

                root = root->left;
            }
            else
            {   if(peakNode != NULL)
                {
                    lastP = peakNode;
                    lastNodeVal = peakNode->val; 
                }
            
                peakNode = stk.top();
                if(peakNode->val < lastNodeVal)
                {
                    if(flag1 == false )
                    {
                        flag1 = true;
                        P1 = lastP;
                        NodeVal1 = P1->val;
                        P2 = peakNode;
                        NodeVal2 = P2->val;
                    }
                  else
                    {
                        P1->val = peakNode->val;
                        peakNode->val = NodeVal1; 
                        return; 
                    }
                }
                
                 stk.pop();
                 root = peakNode->right; 
                
            }
        }
        if(flag2 == false)
        {
           P1->val = NodeVal2;
           P2->val = NodeVal1;
           
        }
        return; 
    }
    

    };


Log in to reply
 

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