[Leetcode][JAVA] Recover Binary Search Tree (Morris Inorder Traversal)

浏览数：27 / 时间：2015年06月08日

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(n)空间的话可以直接中序遍历来找问题节点。

如果是O(1)空间的话，基本上就只能是原地操作了。

这里介绍一个Morris Inorder Traversal。可以实现：

1. 如果当前节点有左子树，那么找到左子树的最右节点并把它右指针指向当前节点。当前节点转移到其左节点。

2. 如果左子树的最右节点已经指向了当前节点（之前已经遍历过左子树），那么还原最右节点的右指针为null, 输出当前节点，当前节点转移到其右节点。

3. 如果当前节点没有左子树，那么直接输出当前节点并将其转移到右节点。

写成代码如下：

 1     public void recoverTree(TreeNode root) {
 2         TreeNode cur = root;
 3         while(cur!=null) {
 4             if(cur.left!=null) {
 5                 TreeNode temp = cur.left;
 6                 while(temp.right!=null && temp.right!=cur)
 7                     temp = temp.right;
 8                 if(temp.right==null) {
 9                     temp.right = cur;
10                     cur = cur.left;
11                 }
12                 else {
13                     temp.right=null;
14                     //print
15                     cur=cur.right;
16                 }
17             }
18             else {
19                 //print
20                 cur=cur.right
21             }
22         }
23     }
24 }

结合这道题，只需要在print的地方添加代码即可。

只存在一处错误，遍历时可能出现两种情况：

1. 发现一次原先节点值比当前节点值大，例如：（1, 4, 3, 7, 9）这时只有对调这两个节点值即可。

2. 发现两次原先节点值比当前节点值大，例如：（1, 9, 4, 5, 3, 10）这时需要对调第一次的原先节点值和第二次的当前节点值。

使用两个TreeNode wrong1, wrong2记录这两个错误节点，如果是第一次发现原先节点比当前节点值大的错误，则wrong1置为原先节点，wrong2置为当前节点。如果又发现一次，则只更改wrong2.

注意原先节点pre和当前节点cur的关系，只有cur即将挪向右节点之前才将pre置为cur. (因为cur挪向左节点是第一次遍历左子树，仅仅用来连接，第二次遍历才输出)

完整代码如下：

 1     public void recoverTree(TreeNode root) {
 2         TreeNode cur = root;
 3         TreeNode pre = null;
 4         TreeNode wrong1 = null;
 5         TreeNode wrong2 = null;
 6         while(cur!=null) {
 7             if(cur.left!=null) {
 8                 TreeNode temp = cur.left;
 9                 while(temp.right!=null && temp.right!=cur)
10                     temp = temp.right;
11                 if(temp.right==null) {
12                     temp.right = cur;
13                     cur = cur.left;
14                 }
15                 else {
16                     temp.right=null;
17                     //print
18                     if(pre!=null && pre.val>cur.val) {
19                         if(wrong1==null)
20                             wrong1=pre;
21                         wrong2 = cur;
22                     }
23                     pre = cur;
24                     cur=cur.right;
25                 }
26             }
27             else {
28                 //print
29                 if(pre!=null && pre.val>cur.val) {
30                     if(wrong1==null)
31                         wrong1=pre;
32                     wrong2 = cur;
33                 }
34                 pre = cur;
35                 cur=cur.right;
36             }
37         }
38         int t = wrong1.val;
39         wrong1.val = wrong2.val;
40         wrong2.val = t;
41     }