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