Can someone help locate the problem? Thank you!


  • 0
    B

    I use Morris Traversal to solve the problem. I think it is enough to break the outer loop after finding both numbers. However, I got MLE with this solution. But when I commented out two "break" in the code, I can pass the OJ. I have no idea what happens here, can someone help? Thank you so much!

    public class Solution {
          public void recoverTree(TreeNode root) {
            if (root == null) {
              return;
            }
        
            TreeNode cur = root;
            TreeNode  prev = null;
            TreeNode firstNum = null;
            TreeNode secondNum = null;
            while (cur != null) {
              if (cur.left == null) {  
                if (prev != null && cur.val < prev.val) {
                  if (firstNum == null) {
                    firstNum = prev;
                    secondNum = cur;
                  } else {
                    secondNum = cur;
                    break;  // comment out can pass
                  }
                } 
                prev = cur;
                cur = cur.right;
              } else {
                TreeNode preceding = cur.left;
                while (preceding.right != null && preceding.right != cur) {
                  preceding = preceding.right;
                }
                if (preceding.right == null) { 
                  preceding.right = cur;  
                  cur = cur.left;
                } else { 
                  if (prev != null && cur.val < prev.val) {
                    if (firstNum == null) {
                      firstNum = prev;
                      secondNum = cur;
                    } else {
                      secondNum = cur; 
                      break;  // comment out can pass
                    }
                  }
                  preceding.right = null;
                  prev = cur;
                  cur = cur.right; 
                }
              }
        
            }
            swap(firstNum, secondNum);
          }
        
          private void swap(TreeNode node1, TreeNode node2) {
            int tmp = node1.val;
            node1.val = node2.val;
            node2.val = tmp;
          }
        }

Log in to reply
 

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