第三周主题：树 之 Linked List Cycle in LeetCode (in java)

题目：

http://oj.leetcode.com/problems/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?


/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */


(一个二叉树的两个元素被错误的交换了，在不改变结构的前提下修复这个二叉树)




解答：

O(1)挺难的，想了很久。

这个解法的关键点是中序遍历inorder travel如何才能不使用栈。查了很久，才明白这个要用十多年前数据结构课上，杀手曾经教过的线索二叉树Threaded Binary Tree。




关键点中的关键是：给每一个现在访问的节点current临时再找一个parent节点，该parent节点是其中序遍历时紧邻前面的一个节点，parent.right=current，有这样的临时parent，中序遍历时就不需要栈了。



那么这个parent节点在哪呢？应该是current节点为root的左子树最右边的那个节点。



怎么找这个parent节点呢？

我们这么来:

(1)如果左边走不动了（current.left==null）就往右边走

parent=current; current=current.right;

(2)当往左边可以走时，先找一个临时的pre=current.left;

让后让这个pre一直找.right，pre.right=null为止，这时pre就是current节点为root的左子树最右边的那个节点，就可以设while (pre.right!=null){


     pre = pre.right;

    }

(3) 但这里有个问题，你设了pre.right=current; 不就破坏了树的结构了吗？而且pre也没有被current走到过啊（current=pre的时候才算走到）。于是需要在这里做一个判断：

(3-1) if (pre.right == null){ pre.right = current; current = current.left;} 设定好临时parent，并且继续往左走；

(3-2) if (pre.right == current) {pre.right=null; parent = current; current=current.right;} pre.right == current说明该current左边的路已经走过了，该走右边了。过河拆桥，pre.right=null;

(4) (2)里面循环条件改为while (pre.right!=null && pre.right != current){


        pre = pre.right;

       }

这样我们就有了不需要栈遍历树的算法。

接下来就是找到两个错误点了，在每次往右走之前做个判断看看parent.val是否大于current.val，如果大于的话就是错误点。

但如果找到第二个点的话，怎么知道这是第二个，不是第一个呢？引入一个变量found=false，找到第一个之后，就设为true。

注意，node1=parent，node2=current。因为node1肯定是两者里的大数，node2肯定是两者里的小数。


if (parent!=null && parent.val > current.val){

           if (!found){

            node1 = parent;

            found = true;

           }

           node2 = current;

}

遍历完树之后，swap node1和node2就行了。

这样就圆满了，oh yeah！

References:

[1] 代码在

https://github.com/RockyNiu/LeetCode/blob/master/src/leetcode/java/RecoverBinarySearchTree.java