算法

1.一个包含1-100数字的数组中，有一个数字丢失了，如何快速的找出它？

　　解决思路：1）计算1-100所有数字之和sum；

　　　　　　　2）计算这个数组所有值之和sum2；

　　　　　　　3）缺失的数字为num=sum-sum2。

2.在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

　　解决思路：从头至尾遍历数组，比较当前遍历的数x是否与下标i相等，若i与x相等则i++比较下一个数字，若不相等，则将x与其对应位置的数（x大小位置）进行比较，若相等则该数为重复数字然后i++比较下一个数字，如不相等则将x与其大小位置的数进行交换，i++比较下一个数字。

3.输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点，只调整指针的指向。

思路：以中序遍历访问二元查找树，比较小的节点先访问，对小节点的先处理，定义双向链表的头和尾，当头尾节点为空时，转换节点时，先让头尾指向同一个节点，以后再从尾部插入。

public class BSTreeToList {
    private int value;
    BSTreeToList leftChild;
    BSTreeToList rightChild;
    private BSTreeToList head; //链表头结点
    private BSTreeToList tail; //链表尾节点
    
    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public BSTreeToList getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(BSTreeToList leftChild) {
        this.leftChild = leftChild;
    }

    public BSTreeToList getRightChild() {
        return rightChild;
    }

    public void setRightChild(BSTreeToList rightChild) {
        this.rightChild = rightChild;
    }

    //二叉树中插入数据
    public BSTreeToList add(BSTreeToList root,int value){
        if(root==null){
            root = new BSTreeToList();
            root.setLeftChild(null);
            root.setRightChild(null);
            root.setValue(value);
            return root;
        }
        
        //如果root不为null
        if(root.getValue()>value){
            root.setLeftChild(add(root.getLeftChild(), value)); 
        }else{
            root.setRightChild(add(root.getRightChild(), value));
        }
        return root;
    }
    
    //中序遍历
    public void traverse(BSTreeToList root){
        if(root==null){return;}
        traverse(root.getLeftChild());
        System.out.print(root.getValue()+" ");
        traverse(root.getRightChild());
    }
    
    //转换成链表
    public void transition(BSTreeToList root){
        if(root==null) return;
        transition(root.getLeftChild());
        changeNode(root);
        transition(root.getRightChild());
    }
    
    public void changeNode(BSTreeToList node){
        if(head==null){
            head = node;
            tail = node;
        }else{
            node.leftChild = tail;
            tail.rightChild = node;
            tail = node;
        }
    }
    
    public void preTraverse(){
        while(head!=null){
            System.out.print(head.getValue()+" ");
             head = head.rightChild ;
        }
    }
    
    public void sufTraverse(){
        while(tail!=null){
            System.out.print(tail.getValue()+" ");
            tail = tail.leftChild;
        }
    }
    
    
    public static void main(String[] args) {
        BSTreeToList bsTreeToList = new BSTreeToList();
        BSTreeToList root =new BSTreeToList();
        root.setValue(9);
        root.setLeftChild(null);
        root.setRightChild(null);
        int []s = new int[]{1,4,8,10,2,5};
        for(int i =0;i<s.length;i++){
            bsTreeToList.add(root, s[i]);
        }
        System.out.print("中序遍历"+"  ");
        bsTreeToList.traverse(root);
        bsTreeToList.transition(root);
        System.out.println();
        System.out.print("链表从头至尾遍历"+"  ");
        bsTreeToList.preTraverse();
        System.out.println();
        System.out.print("链表从尾至头遍历"+"  ");
        bsTreeToList.sufTraverse();
    }
}

运行结果：