一、算法基础
1. 重建二叉树
题目：
输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。
注意：
- 二叉树中每个节点的值都互不相同；
- 输入的前序遍历和中序遍历一定合法；
演示：
给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]
分析：
前序的第一个字母肯定是父节点, 然后再去中序找该节点对应的位置, 位置前是左子树, 后是右子树。以此类推。
代码：
2. 替换空格
题目：
请实现一个函数，把字符串中的每个空格替换成"%20"。
你可以假定输入字符串的长度最大是1000。 注意输出字符串的长度可能大于1000。
演示：
分析：
考察对char的处理
代码：
3. 二叉搜索树的后序遍历序列
题目：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则返回true，否则返回false。
假设输入的数组的任意两个数字都互不相同。
演示：
分析：
后序遍历的特点是根在最后, 拿这个为突破点, 因为是搜索树, 所以自然有序, 拿到不符合有序的交界节点, 则其前应为小数升序, 其后为大数升序, 不满足则返回false
代码：
4. 二叉树中和为某一值的路径
题目：
输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
演示：
给出二叉树如下所示，并给出num=22。
输出：
代码：
5. 斐波那契数列
题目：
输入一个整数 n ，求斐波那契数列的第 n 项。
假定从0开始，第0项为0。(n<=39)
演示：
分析：
最基础的做法就是用递归， 进阶做法用动态规划
代码：
6. 跳台阶
题目：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
代码：
7. 栈的压入、弹出序列
题目：
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
假设压入栈的所有数字均不相等。
例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
注意：若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空，则视为是一个栈的压入、弹出序列。
演示：
输入：
输出：true
分析：
用一个真实的栈来辅助, 当pop的值和弹出序列的某个数相等&&栈不为空, 则弹出这个数。最后看栈是否为空, 如果不是正确的压入弹出顺序, 栈是空不了的。
代码：
8. 二叉搜索树的后序遍历序列
题目：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则返回true，否则返回false。
假设输入的数组的任意两个数字都互不相同。
演示：
分析：
后序遍历的特点是根在最后, 拿这个为突破点, 因为是搜索树, 所以自然有序, 拿到不符合有序的交界节点, 则其前应为小数升序, 其后为大数升序, 不满足则返回false
代码：
9. 二叉树的镜像
题目：
输入一个二叉树，将它变换为它的镜像。
演示：
输入树：
输出树：
分析：
递归思想, 交换当前节点的左右子节点, 然后遍历整个树
代码：
Java面试宝典
1. Java基本概念
2. 面向对象编程
3. 关键字
4. 基本类型与运算
5. 字符串与数组
6. 输入输出流
7. 集合类
8. Java平台与内存管理
9. 异常处理
10. XML
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/1210.html