\描述：

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

}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/150293.html