第1题：把二叉搜索树转换为一个排序的双向链表

欢迎转载，转载请务必注明出处：http://blog.csdn.net/alading2009/article/details/44494693

马上找工作了，准备好好学习下July大神整理的微软面试100题系列，代码使用Java实现（IntelliJ那个黑色主题真是程序员的大爱），顺便就复习一下Java和数据结构。闲话不多说，热腾腾的题和代码端上来。

第一题：把二叉搜索树转换为一个排序的双向链表
要求：不能创建新的节点，只能调整指针的指向

从二叉搜索树的定义来看，root节点左子树上的值都是比它小的，右子树的值都是比它大的，所以变成双向链表后它的左邻居就应该是左子树中值最大的节点，右邻居就是右子树中值最小的节点。接下来就是递归求解实现了。

package Exam001;

/**
 * Created by cq on 2015/3/18.
 * 二叉搜索树节点定义
 */
public class BSTreeNode {
    private int value;
    private BSTreeNode left;
    private BSTreeNode right;
    public BSTreeNode getLeft() {
        return left;
    }
    public void setLeft(BSTreeNode left) {
        this.left = left;
    }
    public int getValue() {
        return value;
    }
    public void setValue(int value) {
        this.value = value;
    }
    public BSTreeNode getRight() {
        return right;
    }
    public void setRight(BSTreeNode right) {
        this.right = right;
    }
    public BSTreeNode(int value){
        this.value=value;
    }
}

package Exam001;

/**
 * Created by cq on 2015/3/18.
 * 第一题：把二叉搜索树转换为一个排序的双向链表
 * 要求：不能创建新的节点，只能调整指针的指向
 */
public class BSTree {
    public BSTreeNode bstree;
    //使用前序遍历打印二叉搜索树
    public void printBSTree(BSTreeNode bst){
        if (bst == null){
            return;
        }
        printBSTree(bst.getLeft());
        System.out.print(bst.getValue()+" ");
        printBSTree(bst.getRight());
    }
    public BSTreeNode getDualLinkedList(BSTreeNode bst){
        if (bst == null){
            return null;
        }
        tree2List(bst);
        return getMinNode(bst);
    }
    //二叉搜索树转为有序双向链表
    public void tree2List(BSTreeNode bst){
        if (bst == null){
            return;
        }

        if (bst.getLeft() != null){
            tree2List(bst.getLeft());
            bst.setLeft(getMaxNode(bst.getLeft()));
            bst.getLeft().setRight(bst);
        }
        if (bst.getRight() != null){
            tree2List(bst.getRight());
            bst.setRight(getMinNode(bst.getRight()));
            bst.getRight().setLeft(bst);
        }
    }
    //获取树中最大节点
    public BSTreeNode getMaxNode(BSTreeNode bst){
        if (bst == null){
            return null;
        }
        while (bst.getRight() != null){
            bst = bst.getRight();
        }
        return bst;
    }
    //获取树中最小节点
    public BSTreeNode getMinNode(BSTreeNode bst){
        if (bst == null){
            return null;
        }
        while (bst.getLeft() != null){
            bst = bst.getLeft();
        }
        return bst;
    }
    //打印双向链表
    public void printDualLinkedList(BSTreeNode dList){
        if (dList == null){
            return;
        }

        System.out.print("正向打印双向链表：");
        while(dList.getRight() != null){
            System.out.print(dList.getValue()+" ");
            dList = dList.getRight();
        }
        System.out.print(dList.getValue()+" ");

        System.out.print("
反向打印双向链表：");
        while (dList.getLeft() != null){
            System.out.print(dList.getValue()+" ");
            dList = dList.getLeft();
        }
        System.out.print(dList.getValue()+" ");

    }
    public static void main(String[] args){
        BSTree bst = new BSTree();
        bst.bstree = new BSTreeNode(10);
        BSTreeNode node2 = new BSTreeNode(6);
        BSTreeNode node3 = new BSTreeNode(14);
        BSTreeNode node4 = new BSTreeNode(4);
        BSTreeNode node5 = new BSTreeNode(8);
        BSTreeNode node6 = new BSTreeNode(12);
        BSTreeNode node7 = new BSTreeNode(16);
        bst.bstree.setLeft(node2);
        bst.bstree.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        node3.setRight(node7);

        System.out.print("前序遍历二叉搜索树：");
        bst.printBSTree(bst.bstree);
        System.out.println();

        BSTreeNode tmp = bst.getDualLinkedList(bst.bstree);
        bst.printDualLinkedList(tmp);
    }
}

先这样，后面再看看有没有什么可以改进的地方。