（1）输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

/** * Definition for binary tree * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {   public TreeNode reConstructBinaryTree(int [] pre,int [] in) {        return _reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);    }    private TreeNode _reConstructBinaryTree(int [] pre, int preLeft, int preRight, int [] in, int inLeft, int inRight) {        int i;        for (i = inLeft; i <= inRight; i++) { //找到根节点所在位置            if (pre[preLeft] == in[i]) {                break;            }        }        TreeNode node = new TreeNode(pre[preLeft]);         boolean leftFlag = true;        boolean rightFlag = true;        if (i == inLeft) { //如果左子树节点数为0，也就是没有左子树            leftFlag = false;        }        if (i == inRight) { //如果右子树节点数为0，也就是没有右子树            rightFlag = false;        }        int leftNum = i - inLeft; //计算根节点左子树有几个节点        if (leftFlag) {            //System.out.println((preLeft + 1) + " " + (preLeft + leftNum) + " " + inLeft + " " + (i - 1));            node.left = this._reConstructBinaryTree(pre, preLeft + 1, preLeft + leftNum, in, inLeft, i - 1);        }        if (rightFlag) {            //System.out.println((preLeft + leftNum + 1) + " " + (preRight) + " " + (i + 1) + " " + (inRight));            node.right = this._reConstructBinaryTree(pre, preLeft + leftNum + 1, preRight, in, i + 1, inRight);        }        return node;    } }

（2）用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

import java.util.Stack;public class Solution {    Stack
     
       stack1 = new Stack
      
       ();    Stack
       
         stack2 = new Stack
        
         ();        public void push(int node) {         stack1.push(node);    }        public int pop() {        while (!stack1.empty()) {            stack2.push(stack1.pop());        }        int num = stack2.pop();        while (!stack2.empty()) {            stack1.push(stack2.pop());        }        return num;    }}
        
       
      
     

（3）把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

import java.util.ArrayList;public class Solution {    public int minNumberInRotateArray(int [] array) {        if (array.length == 0) {            return 0;        }        int i = 0;        while (i < array.length) {            //找到第一个小于前一个数的数            if ((i + 1) < array.length && array[i] <= array[i + 1]) {                i++;            } else {                break;            }        }        return  (i + 1) < array.length ? array[i + 1] : array[0];           }}

（4）一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

public class Solution {    public int JumpFloor(int target) {        if (target <= 2) {            return target;        }        return JumpFloor(target - 1) + JumpFloor(target - 2);    }}

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

import java.lang.Math;public class Solution {    public int JumpFloorII(int target) {           return (int)Math.pow(2, target - 1);    }}

（5）输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

public class Solution {    public int NumberOf1(int n) {        int mask = 1, num = 0;        for (int i = 1; i < 32; i++) {            int t = (int)(mask & n);            if (t > 0) {                num++;            }            mask <<= 1;        }        return num;    }}

（6）输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/**public class TreeNode {    int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {        this.val = val;    }}*/import java.util.Queue;public class Solution {    public boolean HasSubtree(TreeNode root1,TreeNode root2) {        if (root2 == null || root1 == null) {            return false;        }         return IsContain(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);       }        //判断root2是否是root1的子结构    private boolean IsContain(TreeNode root1,TreeNode root2) {        if (root2 == null) {            return true;        }        else if (root1 == null) {            return false;        }        else {            return root1.val == root2.val && IsContain(root1.left, root2.left) && IsContain(root1.right, root2.right);        }    }}

（7）

查找最晚入职员工的所有信息

select * from employees order by hire_date desc limit 1;

查找入职员工时间排名倒数第三的员工所有信息

select * from employees order by hire_date desc limit 2,1;