\描述：
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
思路：
题上给了我们前序遍历(根 左 右)和中序遍历(左 根 右)，因为前序遍历先遍历根，故可以通过前序遍历确定根，再由中序遍历确定根的左右子树是什么.循环往复（递归），直到整个树构建完成。
解题步骤：
1.需要递归，题中给的函数无法满足要求，因此我们需要自己创建一个函数（buildTree）。
2.在递归过程中，需要确认根节点的下标，因此我们又需要再创建一个函数（findIndex）。
3.递归需要有结束条件，当instart下标不再大于inend下标时，证明所有的节点都已经归位，因此用instart>inend作为终止递归条件。
代码如下：
public class Solution { int i=0;//根的下标 public TreeNode reConstructBinaryTree(int [] pre,int [] vin) { return buildTree(pre,vin,0,vin.length-1); } private TreeNode buildTree(int [] pre,int[] vin,int instart,int inend) { //递归终止条件 if(instart>inend) { return null; } int mid=findIndex(vin,instart,inend,pre[i]); TreeNode root=new TreeNode(pre[i]); i++; root.left=buildTree(pre,vin,instart,mid-1); root.right=buildTree(pre,vin,mid+1,inend); return root; } private int findIndex(int[] vin,int instart,int inend,int key) { //找每一个子树的根 for(int j=instart;j<=inend;j++) { if(vin[j]==key) { return j; } } return -1; }
JZ9 用两个栈实现队列
描述
用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。
思路：
我们知道栈是先进后出，队列是先进先出。 我们可以建立两个栈（stack1，stack2），让他两个一个负责入栈，一个负责出栈，逻辑也简单，
入栈：只需要进一个元素push一个元素就行了。
出栈：队列的话，应该是第一个进入的第一个出去，现在第一个进入的在栈底，故我们需要将栈底的元素挪到栈顶，这就stack1中的所有元素从栈顶全部入到stack2，直到stack1中为空。再将去stack2中的栈顶取出先存起来。因为还有元素会加入到队列当中，故我们需要再将stack2中的元素再次导入stack1。
pop（）函数
解题步骤：
1.建立两个栈。
2.将进入的元素都入到stack1，这就完成了push（）；
3.在pop（)函数中倒置stack1与stack2就完成了该函数。
代码如下：
import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { stack1.push(node); } public int pop() { int tmp=0; while(!stack1.isEmpty()) { tmp=stack1.pop(); stack2.push(tmp); } int ret=stack2.pop(); while(!stack2.isEmpty()) { tmp=stack2.pop(); stack1.push(tmp); } return ret; } }
