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

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. 如果当前节点没有左子树，那么直接输出当前节点并将其转移到右节点。

写成代码如下：

     public void recoverTree(TreeNode root) {

         TreeNode cur = root;

         while(cur!=null) {

             if(cur.left!=null) {

                 TreeNode temp = cur.left;

                 while(temp.right!=null && temp.right!=cur)

                     temp = temp.right;

                 if(temp.right==null) {

                     temp.right = cur;

                     cur = cur.left;

                 }

                 else {

                     temp.right=null;

                     //print

                     cur=cur.right;

                 }

             }

             else {

                 //print

                 cur=cur.right

             }

         }

     }

 }

结合这道题，只需要在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挪向左节点是第一次遍历左子树，仅仅用来连接，第二次遍历才输出)

完整代码如下：

     public void recoverTree(TreeNode root) {

         TreeNode cur = root;

         TreeNode pre = null;

         TreeNode wrong1 = null;

         TreeNode wrong2 = null;

         while(cur!=null) {

             if(cur.left!=null) {

                 TreeNode temp = cur.left;

                 while(temp.right!=null && temp.right!=cur)

                     temp = temp.right;

                 if(temp.right==null) {

                     temp.right = cur;

                     cur = cur.left;

                 }

                 else {

                     temp.right=null;

                     //print

                     if(pre!=null && pre.val>cur.val) {

                         if(wrong1==null)

                             wrong1=pre;

                         wrong2 = cur;

                     }

                     pre = cur;

                     cur=cur.right;

                 }

             }

             else {

                 //print

                 if(pre!=null && pre.val>cur.val) {

                     if(wrong1==null)

                         wrong1=pre;

                     wrong2 = cur;

                 }

                 pre = cur;

                 cur=cur.right;

             }

         }

         int t = wrong1.val;

         wrong1.val = wrong2.val;

         wrong2.val = t;

     }

巴特西

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

最新文章

热门文章