99. Recover Binary Search Tree.md

99. Recover Binary Search Tree

---

leetcode-cn Daily Challenge on August 8th, 2020.

---

Difficulty : Hard

Related Topics : DFS、Tree

---

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2:

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

• A solution using O(n) space is pretty straight forward.
• Could you devise a constant space solution?

---

Solution

• mine
  • Java
    • Runtime: 3 ms, faster than 52.79%, Memory Usage: 40.2 MB, less than 42.71% of Java online submissions

      // O(N *logN)time
      // O(N)space
      int index = 0;
      public void recoverTree(TreeNode root) {
          List<Integer> list = new ArrayList<>();
          dfs(root, list);
          Collections.sort(list);
          update(root,list);
      }
      
      void dfs(TreeNode node, List<Integer> list){
          if(node == null) return;
          dfs(node.left, list);
          list.add(node.val);
          dfs(node.right, list);
      }
      
      void update(TreeNode node, List<Integer> list){
          if(node == null) return;
          update(node.left, list);
          node.val = list.get(index++);
          update(node.right, list);
      }
      

---

• Leetcode Solution

• Implicit Inorder Traversal Runtime: 2 ms, faster than 84.70%, Memory Usage: 40 MB, less than 51.72% of Java online submissions

  // O(N)time
  // O(D)space
  public void recoverTree(TreeNode root) {
      Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
      TreeNode x = null, y = null, pred = null;
  
      while (!stack.isEmpty() || root != null) {
          while (root != null) {
              stack.push(root);
              root = root.left;
          }
          root = stack.pop();
          if (pred != null && root.val < pred.val) {
              y = root;
              if (x == null) {
                  x = pred;
              } else {
                  break;
              }
          }
          pred = root;
          root = root.right;
      }
  
      swap(x, y);
  }
  
  public void swap(TreeNode x, TreeNode y) {
      int tmp = x.val;
      x.val = y.val;
      y.val = tmp;
  }
  

• Morris Inorder Traversal Runtime: 1 ms, faster than 100.00%, Memory Usage: 40 MB, less than 51.72% of Java online submissions

  // O(N)time
  // O(1)space
  public void recoverTree(TreeNode root) {
      TreeNode x = null, y = null, pred = null, predecessor = null;
  
      while (root != null) {
          if (root.left != null) {
              // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
              predecessor = root.left;
              while (predecessor.right != null && predecessor.right != root) {
                  predecessor = predecessor.right;
              }
  
              // 让 predecessor 的右指针指向 root，继续遍历左子树
              if (predecessor.right == null) {
                  predecessor.right = root;
                  root = root.left;
              }
              // 说明左子树已经访问完了，我们需要断开链接
              else {
                  if (pred != null && root.val < pred.val) {
                      y = root;
                      if (x == null) {
                          x = pred;
                      }
                  }
                  pred = root;
  
                  predecessor.right = null;
                  root = root.right;
              }
          }
          // 如果没有左孩子，则直接访问右孩子
          else {
              if (pred != null && root.val < pred.val) {
                  y = root;
                  if (x == null) {
                      x = pred;
                  }
              }
              pred = root;
              root = root.right;
          }
      }
      swap(x, y);
  }
  
  public void swap(TreeNode x, TreeNode y) {
      int tmp = x.val;
      x.val = y.val;
      y.val = tmp;
  }
  

---