【剑指offer】JZ7 重建二叉树、JZ9 用两个栈实现队列

\描述： 

给定节点数为 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;}}