题目:输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果都不含重复的数字。例如:输入的前序遍历列 {1, 2, 4, 7, 3, 5, 6, 7} 和中序遍历列 {4, 7, 2, 1, 5, 3, 8, 6},则重建如图所示的二叉树,并输出它的头节点。二叉树定义如下:
根据前序遍历的特点:第一个数字总是树的根节点的值。但在中序遍历中,根节点的值在序列的中间,左子树的节点的值位于根节点的左边,右子树的节点的值位于根节点的值的右边。
所以根据已知的前序遍历和中序遍历的序列值,可以知道,在中序遍历的序列值在 1 左边的 3 个数即 {4, 7, 2} 是二叉树的左子树,1 后面的四个数即 {5, 3, 8, 6} 是二叉树的右子树。
得到左子树和右子树后,现在我们可以将左右子树分别看成单独的二叉树,根据前序遍历的特点,又可以得到 2 是左子树的根节点,3 是右子树的根节点。
依次以递归的方法去完成,就能得到重建二叉树。
......后续补充
本题考点:
题目:给定一棵二叉树和其中的一个节点,如何找出中序遍历列的下一个节点?
......后续补充
本题考点:
题目:用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead,分别完成在队列尾部插入节点和在队列头部删除节点的功能。
两个栈是很自然的就能实现从“先进后出”到“先进先出”的。
......后续补充
题目一:求斐波拉契数列的第 n 项。
写一个函数,输入 n,求斐波拉契数列的第 n 项。
使用递归函数求解。例如:我们以求解 f(10) 为例来分析递归的求解过程。想得到 f(10),需要先求得 f(9) 和 f(8)。同时要求 f(9) 需要求得 f(8) 和 f(7)······
不难发现,很多是重复计算的。重复的节点数会随着 n 的增大而急剧增加,以为这计算量会随着 n 的增大而急剧增大。事实上,用递归方法计算的时间复杂度是一 n 的指数方式递增的。
更简单的方法是从下往上计算,首先根据 f(0) 和 f(1) 算出 f(2),再根据 f(1) 和 f(2) 计算出 f(3)······以此类推计算出第 n 项。所以可以利用循环来实现。
......后续补充
题目二:青蛙跳台阶问题。
一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级台阶。求该青蛙跳上一个 n 级台阶共有多少种跳法。
本题考点:
原文:https://www.cnblogs.com/reformdai/p/11134756.html