首页 > 代码库 > [Leetcode][JAVA] Recover Binary Search Tree (Morris Inorder Traversal)
[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. 如果当前节点没有左子树，那么直接输出当前节点并将其转移到右节点。
写成代码如下：
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 //print15 cur=cur.right;16 }17 }18 else {19 //print20 cur=cur.right21 }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 //print18 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 //print29 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 }
[Leetcode][JAVA] Recover Binary Search Tree (Morris Inorder Traversal)