将二叉搜索树改变为双向链表

剑指offer面试题系列

题目：输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向，比如输入左边的二叉树，输出转换之后的排序双向链表。

  二叉搜索树                    双向链表

     10
  6     14                 4--6--8--10--12--14--16(此处为了简便，将双向箭头做了简化)
4  8   12 16                                              

分析

原始的二叉搜索树如图所示

解决此题的关键点：1.将二叉树结点的right和left指针与双向链表的前后指针对应起来；2.改变指针的时候，root指针的指向与他的left或者right是叶子节点还是一棵子树有很大关系，相应的改变方法也稍有不同。而改变方法的关键点在于深刻理解二叉搜索树的中序遍历原理。

如果 root 结点的左孩子是叶子节点，则直接改变指针指向即可；如果 root 结点的左孩子是一棵树，则需要找到这棵树最右边的节点，这个节点在中序遍历时，也是与结点紧挨着的前面的结点；同理，右孩子也一样，如果是子树的话，需要找到右子树的最左边的结点。

改变指针关系如图所示

改造后的双向链表模型如图

开始拿到这个题的时候想着递归遍历到最左边的结点时，然后再改变指向关系，可是发现当你遍历到一个叶子结点的时候，无法指向父节点。所以递归的结束条件是遍历到叶子节点。

代码实现

主要代码如下：

/* 将二叉排序树转换成双向链表 */
    public static void ConverseToList(TreeNode root) {
        if (isLeaf(root)) // Leaf Node
            return;
        if (root.left != null) {
            ConverseToList(root.left);
            if (isLeaf(root.left)) { // Left child is Leaf Node
                root.left.right = root;
            } else { // has sub-left tree
                // find the right most node
                TreeNode RightEdge = root.left;
                while (RightEdge.right != null) {
                    RightEdge = RightEdge.right;
                }
                root.left = RightEdge;
                RightEdge.right = root;
            }
        }
        if (root.right != null) {
            ConverseToList(root.right);
            if (isLeaf(root.right)) {
                root.right.left = root;
            } else { // has sub-right tree
                // find the left most node
                TreeNode LeftEdge = root.right;
                while (LeftEdge.left != null) {
                    LeftEdge = LeftEdge.left;
                }
                root.right = LeftEdge;
                LeftEdge.left = root;
            }
        }
    }

    public static boolean isLeaf(TreeNode node) {
        if (node != null && node.left == null && node.right == null)
            return true;
        return false;
    }


    /*打印双向链表*/
    public static void PrintList(TreeNode root) {
        //find the left start
        TreeNode head = root;
        while(head.left != null) {
            head = head.left;
        }

        //begin to print from left to right
        System.out.println("Print from left to right");
        while(head.right != null) {
            System.out.print(head.data + "----");
            head = head.right;
        }
        System.out.println("NULL");

        //print from right to left
        System.out.println("Print from right to left");
        while(head != null) {
            System.out.print(head.data + "----");
            head = head.left;
        }
        System.out.println("NULL");

    }

总结

现在对于理解和使用递归这种方法，稍微有点感觉了，继续保持。但是在纸上写程序的功底较差，要在这方面加强。