Recover Binary Search Tree

描述

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

Recover the tree without changing its structure.

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

分析

O(logn)空间的解法是，中序递归遍历，用两个指针存放在遍历过程中碰到的两处逆向的位置。

本题要求O(1)空间，只能用Morris中序遍历。

中序遍历，递归方式

  1. // Recover Binary Search Tree
  2. // 中序遍历,递归
  3. // 时间复杂度O(n)，空间复杂度O(logn)
  4. // 本代码仅仅是为了帮助理解题目
  5. public class Solution {
  6.     private TreeNode p1 = null;
  7.     private TreeNode p2 = null;
  8.     private TreeNode prev = null;
  10.     public void recoverTree(TreeNode root) {
  11.         inOrder( root);
  12.         // swap
  13.         int tmp = p1.val;
  14.         p1.val = p2.val;
  15.         p2.val = tmp;
  16.     }
  18.     private void inOrder(TreeNode root) {
  19.         if ( root ==  null ) return;
  20.         if ( root.left != null ) inOrder(root.left);
  22.         if ( prev != null && root.val < prev.val ) {
  23.             if ( p1 == null) {
  24.                 p1 = prev;
  25.                 p2 = root;
  26.             } else {
  27.                 p2 = root;
  28.             }
  29.         }
  30.         prev = root;
  31.         if ( root.right != null ) inOrder(root.right);
  32.     }
  33. }

Morris中序遍历

  1. // Recover Binary Search Tree
  2. // Morris中序遍历，时间复杂度O(n)，空间复杂度O(1)
  3. public class Solution {
  4.     public void recoverTree(TreeNode root) {
  5.         TreeNode[] broken = new TreeNode[2];
  6.         TreeNode prev = null;
  7.         TreeNode cur = root;
  9.         while (cur != null) {
  10.             if (cur.left == null) {
  11.                 detect(broken, prev, cur);
  12.                 prev = cur;
  13.                 cur = cur.right;
  14.             } else {
  15.                 TreeNode node = cur.left;
  17.                 while (node.right != null && node.right != cur)
  18.                     node = node.right;
  20.                 if (node.right == null) {
  21.                     node.right = cur;
  22.                     //prev = cur; 不能有这句！因为cur还没有被访问
  23.                     cur = cur.left;
  24.                 } else {
  25.                     detect(broken, prev, cur);
  26.                     node.right = null;
  27.                     prev = cur;
  28.                     cur = cur.right;
  29.                 }
  30.             }
  31.         }
  32.         // swap
  33.         int tmp = broken[0].val;
  34.         broken[0].val = broken[1].val;
  35.         broken[1].val = tmp;
  36.     }
  38.     void detect(TreeNode[] broken, TreeNode prev,
  39.                 TreeNode current) {
  40.         if (prev != null && prev.val > current.val) {
  41.             if (broken[0] == null) {
  42.                 broken[0] = prev;
  43.             } //不能用else，例如 {0,1}，会导致最后 swap时second为nullptr，
  44.             //会 Runtime Error
  45.             broken[1] = current;
  46.         }
  47.     }
  48. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/binary-tree/traversal/recover-binary-search-tree.html