本文共 3747 字，大约阅读时间需要 12 分钟。

欢迎转载，转载请务必注明出处：

马上找工作了，准备好好学习下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("\n反向打印双向链表：");        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);    }}

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