4ms Simple and Clean Java Solution using 3 pointers


  • 0
    D
    public class Solution {
      private TreeNode last = null;
      private TreeNode first = null, second = null;
      public void recoverTree(TreeNode root) {
          if (root == null)
              return ;
          recoverTreeHelper(root);
          swap(first, second);
      }
    
      private void recoverTreeHelper(TreeNode root) {
          if (root != null) {
              recoverTreeHelper(root.left);
              if (last != null && last.val > root.val) {
                  if (first == null) {
                      first = last;
                      second = root;
                  } else {
                      second = root;
                  }
              }
              last = root;
              recoverTreeHelper(root.right);
          }
      }
    
      private void swap(TreeNode n1, TreeNode n2) {
          int temp = n1.val;
          n1.val = n2.val;
          n2.val = temp;
      }
    }

  • 0
    P

    You have a recursive function and it is not tail-recursive. I don't think you can do it with constant space.


Log in to reply
 

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