以前单位同事去一家公司的面试题，居然一道都没做全，看看有没有那么难 - 面试秘籍 - Jo...

第一道. 用java 实现二叉树的左遍历


第二道 用科学计数法实现，输入1234返回1,234,输入1234567返回1,234,567,输入12返回
12

第三道 有N+1个不重复数据，一个长度为N的vector数组，vector存放N+1中的数据（vector无重复数据），找出vector中遗漏的那一个数值（即N+1中没有被vector存放的那个值）

public void getValue(Vector n){
...........................(填写)
}

 

回复：

 

第一题：应该是二叉树的前序遍历吧。

public class Tree {

    private int data;// 数据节点
    private Tree left;// 左子树
    private Tree right;// 右子树

    public Tree(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }

    /**
     * 创建二叉树，返回根结点
     *
     * @param input
     * @return
     */
    public static Tree createTree(int[] input) {
        Tree root = null;
        Tree temp = null;
        for (int i = 0; i < input.length; i++) {
            // 创建根节点
            if (root == null) {
                root = temp = new Tree(input[i]);
            } else {
                // 回到根结点
                temp = root;
                // 添加节点
                while (temp.data != input[i]) {
                    if (input[i] <= temp.data) {
                        if (temp.left != null) {
                            temp = temp.left;
                        } else {
                            temp.left = new Tree(input[i]);
                        }
                    } else {
                        if (temp.right != null) {
                            temp = temp.right;
                        } else {
                            temp.right = new Tree(input[i]);
                        }
                    }
                }
            }
        }
        return root;
    }

    /**
     * 前序遍历
     *
     * @param tree
     */
    public static void preOrder(Tree tree) {
        if (tree != null) {
            System.out.print(tree.data + " ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }

    /**
     * 中序遍历
     *
     * @param tree
     */
    public static void midOrder(Tree tree) {
        if (tree != null) {
            midOrder(tree.left);
            System.out.print(tree.data + " ");
            midOrder(tree.right);
        }
    }

    /**
     * 后序遍历
     *
     * @param tree
     */
    public static void posOrder(Tree tree) {
        if (tree != null) {
            posOrder(tree.left);
            posOrder(tree.right);
            System.out.print(tree.data + " ");
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] input = { 4, 2, 6, 1, 3, 5, 7 };
        Tree tree = createTree(input);
        System.out.print("前序遍历：");
        preOrder(tree);
        System.out.print("\n中序遍历：");
        midOrder(tree);
        System.out.print("\n后序遍历：");
        posOrder(tree);
    }
}

前序遍历：4 2 1 3 6 5 7
中序遍历：1 2 3 4 5 6 7
后序遍历：1 3 2 5 7 6 4