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?

 

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

 

Hide Tags

 SOLUTION 1:

采用递归+全局变量完成：

空间复杂度是O(logn)

REF: http://huntfor.iteye.com/blog/2077665

这一篇讲得蛮清楚：

http://yucoding.blogspot.com/2013/03/leetcode-question-75-recover-binary.html

具体的思路，还是通过中序遍历，只不过，不需要存储每个节点，只需要存一个前驱即可。

例如1,4,3,2,5,6

1.当我们读到4的时候，发现是正序的，不做处理

2.但是遇到3时，发现逆序，将4存为第一个错误节点，3存为第二个错误节点

3.继续往后，发现3，2又是逆序了，那么将第2个错误节点更新为2

如果是这样的序列：1,4,3,5,6同上，得到逆序的两个节点为4和3。

========================================

这里我们补充一下，为什么要替换第二个节点而不是第一个节点：

e.g. The correct BST is below:

The inorder traversal is :  1 3 4 6 7 8 10 13 14

Find the place which the order is wrong.

        Wrong order: 1 3 8 6 7 4 10 13 14     

        FIND:                    8 6

        Then we find:             7 4

        8, 6 是错误的序列, 但是，7，4也是错误的序列。

        因为8，6前面的序列是正确的，所以8，6一定是后面的序列交换来的。

        而后面的是比较大的数字，也就是说8一定是被交换过来的。而7，4

        中也应该是小的数字4是前面交换过来的。

        用反证法来证明：

        假设：6是后面交换过来的

        推论: 那么8比6还大，那么8应该也是后面交换来的，

        这样起码有3个错误的数字了

        而题目是2个错误的数字，得证，只应该是8是交换过来的。

结论就是：我们需要交换的是：8， 4.

1 public class RecoverTree { 2     TreeNode pre = null; 3     TreeNode first = null; 4     TreeNode second = null; 5      6      7     public void recoverTree(TreeNode root) { 8         inOrder(root); 9         10         // swap the value of first and second node.11         int tmp = first.val;12         first.val = second.val;13         second.val = tmp;14     }15     16     public void inOrder(TreeNode root) {17         if (root == null) {18             return;19         }20         21         // inorder traverse.22         inOrder(root.left);23 24         /*25         Find the place which the order is wrong.26         For example: 1 3 4 6 7 8 10 13 1427         Wrong order: 1 3 8 6 7 4 10 13 14      28         FIND:            ___29         Then we find:        ___30         8, 6 是错误的序列, 但是，7，4也是错误的序列。31         因为8，6前面的序列是正确的，所以8，6一定是后面的序列交换来的。 32         而后面的是比较大的数字，也就是说8一定是被交换过来的。而7，433         中也应该是小的数字4是前面交换过来的。34 35         用反证法来证明：36         假设：6是后面交换过来的37         推论: 那么8比6还大，那么8应该也是后面交换来的，38         这样起码有3个错误的数字了39         而题目是2个错误的数字，得证，只应该是8是交换过来的。40         */41 42         // 判断 pre 是否已经设置43         if (pre != null && pre.val > root.val) {44             if (first == null) {45                 // 首次找到反序.46                 first = pre;47                 second = root;48             } else {49                 // 第二次找到反序，更新Second.50                 second = root;51             }52         }53 54         pre = root;55 56         // inorder traverse.57         inOrder(root.right);58     }

SOLUTION 2:

也可以采用非递归方法，不需要加全局变量，空间复杂度是O(logn)：

1 public void recoverTree1(TreeNode root) { 2         if (root == null) { 3             return; 4         } 5          6         TreeNode node1 = null; 7         TreeNode node2 = null; 8          9         TreeNode pre = null; 10         11         Stack
      
        s = new Stack
       
        ();12         TreeNode cur = root;13         14         while (true) {15             while (cur != null) {16                 s.push(cur);17                 cur = cur.left;18             }19             20             if (s.isEmpty()) {21                 break;22             }23             24             TreeNode node = s.pop();25             26             if (pre != null) {27                 // invalid order28                 if (pre.val > node.val) {29                     if (node1 == null) {30                         node1 = pre;31                         node2 = node;32                     } else {33                         node2 = node;34                     }35                 }36             }37             38             pre = node;39             40             cur = node.right;41         }42         43         int tmp = node1.val;44         node1.val = node2.val;45         node2.val = tmp;46         47         return;48     }
       
      

SOLUTION 3:

还有更厉害的作法，可以达到O(1)的空间复杂度。以后再补上。

ref: 

=================

代码请参考主页君的实现：