C++ Morris Inorder Traversal. Passed in VS but runtime error in OJ


  • 0
    H
    class Solution {
    public:
      // Morris Inorder Traversal
      void recoverTree(TreeNode *root) {
    
        vector<TreeNode *> record;
    
        TreeNode *curr = root, *prev = nullptr; 
        while (curr != nullptr) {
          if (curr->left == nullptr) {
            if (!isCompatible(curr, prev)) record.push_back(curr);
            prev = curr;
            // @ jump back to the low level node.
            curr = curr->right;
          }
          else {
            // @ left subtree.
            auto node = curr->left;
            // @ move to the largest right child of the left subtree.
            while (node->right != nullptr && node->right != curr) node = node->right;
    
            if (node->right == nullptr) {
              node->right = curr;       // @ create the link from node to curr.
              curr = curr->left;
            }
            else { // prev->right == curr  
              if (!isCompatible(curr, prev)) record.push_back(curr);
              node->right = nullptr;    // @ remove the link between node and curr.
              prev = curr;
              curr = curr->right;
            }
          }
        }
        swap(record[0]->val, record[1]->val);
      }
    private:
      bool isCompatible(TreeNode *curr, TreeNode *prev) {
        int left = prev ? prev->val : INT_MIN;
        int right = curr->right ? curr->right->val : INT_MAX;
        return (left < curr->val && curr->val < right) || (left > curr->val && curr->val > right);
      }
    };
    

    Input is {1,#,2,3}


Log in to reply
 

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