【好书推荐】《剑指Offer》之硬技能（编程题7~11）
程序员文章站
2022-06-19 17:08:48
本文例子完整源码地址：https://github.com/yu-linfeng/BlogRepositories/tree/master/repositories/sword 《【好书推荐】《剑指Offer》之软技能》 《【好书推荐】《剑指Offer》之硬技能（编程题1~6）》 持续更新，敬请关注 ......
本文例子完整源码地址：https://github.com/yu-linfeng/blogrepositories/tree/master/repositories/sword
持续更新，敬请关注公众号:coderbuff，回复关键字“sword”获取相关电子书。
7.重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。例如：输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}。
定义二叉树节点
1 /**
2 * 二叉树节点
3 * @author okevin
4 * @date 2019/5/30
5 **/
6 public class node<t> {
7 /**
8 * 左孩子
9 */
10 private node left;
11
12 /**
13 * 右孩子
14 */
15 private node right;
16
17 /**
18 * 值域
19 */
20 private t data;
21
22 public node() {
23 }
24
25 public node(t data) {
26 this.data = data;
27 }
28
29 //省略getter/setter方法
30 }
解法一：递归
1 /**
2 * 根据前序遍历序列和中序遍历序列重建二叉树
3 * @author okevin
4 * @date 2019/5/30
5 **/
6 public class solution {
7 public node<integer> buildbinarytree(integer[] preorder, integer[] inorder) {
8 if (preorder.length == 0 || inorder.length == 0) {
9 return null;
10 }
11 node<integer> root = new node<>(preorder[0]);
12 int index = search(0, inorder, root.getdata());
13 root.setleft(buildbinarytree(arrays.copyofrange(preorder, 1, index + 1), arrays.copyofrange(inorder, 0, index)));
14 root.setright(buildbinarytree(arrays.copyofrange(preorder, index + 1, preorder.length), arrays.copyofrange(inorder, index + 1, inorder.length)));
15 return root;
16 }
17
18 /**
19 * 在中序遍历的序列中查询根节点所在的位置
20 * @param start 开始查找的下标
21 * @param inorder 中序遍历序列
22 * @param rootdata 根节点值
23 * @return 节点值在中序遍历序列中的下标位置
24 */
25 private int search(int start, integer[] inorder, integer rootdata) {
26 for (; start < inorder.length; start++) {
27 if (rootdata.equals(inorder[start])) {
28 return start;
29 }
30 }
31 return -1;
32 }
33 }
二叉树的遍历一共分为：前序遍历、中序遍历和后序遍历
前序遍历遍历顺序为：根节点->左节点->右节点
中序遍历遍历顺序为：左节点->根节点->右节点
后序遍历遍历顺序为：左节点->右节点->根节点
例如二叉树：
1
/ \
2 3
/ / \
4 5 6
\ /
7 8
前序遍历结果为：1、2、4、7、3、5、6、8
中序遍历结果为：4、7、2、1、5、3、8、6
后序遍历结果为：7、4、2、5、8、6、3、1
此题给出前序和中序的遍历结果，要求重建二叉树。从前序遍历结果得知，第一个节点一定是根节点。从中序遍历结果可知，根节点左侧一定是其左子树右侧一定是其右子树。
那么可以得到：
第一次：
根据前序遍历结果得知，1为根节点，根据中序遍历结果得知，4、7、2为左子树，5、3、8、6为右子树。
第二次：
根据前序遍历结果得知，2为节点，根据中序遍历，4、7位节点2的左子树，节点2没有右子树。
第三次：
根据前序遍历结果得知，4为节点，根据中序遍历，7为节点4的右子树，节点4没有左子树。
以此类推，根据递归即可构建一颗二叉树。
测试程序
1 /**
2 * 1
3 * / \
4 * 2 3
5 * / / \
6 * 4 5 6
7 * \ /
8 * 7 8
9 * @author okevin
10 * @date 2019/5/30
11 **/
12 public class main {
13 public static void main(string[] args) {
14 integer[] preorder = new integer[]{1, 2, 4, 7, 3, 5, 6, 8};
15 integer[] inorder = new integer[]{4, 7, 2, 1, 5, 3, 8, 6};
16 solution solution = new solution();
17 node<integer> node = solution.buildbinarytree(preorder, inorder);
18 }
19 }
8.二叉树的下一个节点
题目：给定一颗二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？节点中除了两个分别指向左、右子节点的指针，还有一个指向父节点的指针。
分析：熟悉二叉树中序遍历的特点。查找节点的下一个节点，一共有两种情况：一、节点有右子树，节点的下一个节点即为右子树的最左子节点；二、节点没有右子树，此时又要分为两种情况：1、如果节点位于父节点的左节点，节点的下一个节点即为父节点；2、如果节点位于父节点的右节点，此时向上遍历，找到它是父节点的左节点。
节点定义
1 /**
2 * 二叉树节点定义
3 * @author okevin
4 * @date 2019/6/3
5 **/
6 public class node<t> {
7 /**
8 * 值域
9 */
10 private t data;
11
12 /**
13 * 左节点
14 */
15 private node<t> left;
16
17 /**
18 * 右节点
19 */
20 private node<t> right;
21
22 /**
23 * 父节点
24 */
25 private node<t> parent;
26
27 public node() {
28 }
29
30 public node(t data) {
31 this.data = data;
32 }
33 //省略getter/setter方法
34 }
中序遍历情况下，查找二叉树节点的下一个节点
1 /**
2 * 中序遍历情况下，查找节点的下一个节点
3 * @author okevin
4 * @date 2019/6/3
5 **/
6 public class solution {
7 public node getnextnode(node<integer> head) {
8 if (head == null) {
9 return null;
10 }
11 node<integer> p = head;
12 //第一种情况，节点有右子树。节点右子树的最左子节点即为节点中序遍历的下一个节点
13 if (p.getright() != null) {
14 p = p.getright();
15 while (p.getleft() != null) {
16 p = p.getleft();
17 }
18 return p;
19 }
20 //第二种情况，节点没有右子树。仍然有两种情况：一、节点位于父节点的左节点，此时父节点即为节点中序遍历的下一个节点；二、节点位于父节点的右节点，此时一直向上查找，直到是它父节点的左节点
21 while (p.getparent() != null) {
22 if (p == p.getparent().getleft()) {
23 return p.getparent();
24 }
25 p = p.getparent();
26 }
27 return null;
28 }
29 }
测试程序
1 /**
2 * 1
3 * / \
4 * 2 3
5 * / / \
6 * 4 5 6
7 * \ /
8 * 7 8
9 * 中序遍历序列：4,7,2,1,5,3,8,6
10 * @author okevin
11 * @date 2019/6/3
12 **/
13 public class main {
14 public static void main(string[] args) {
15 node<integer> node1 = new node<>(1);
16 node<integer> node2 = new node<>(2);
17 node<integer> node3 = new node<>(3);
18 node<integer> node4 = new node<>(4);
19 node<integer> node5 = new node<>(5);
20 node<integer> node6 = new node<>(6);
21 node<integer> node7 = new node<>(7);
22 node<integer> node8 = new node<>(8);
23 node1.setleft(node2);
24 node1.setright(node3);
25 node2.setleft(node4);
26 node2.setparent(node1);
27 node3.setleft(node5);
28 node3.setright(node6);
29 node3.setparent(node1);
30 node4.setright(node7);
31 node4.setparent(node2);
32 node5.setparent(node3);
33 node6.setleft(node8);
34 node6.setparent(node3);
35 node7.setparent(node4);
36 node8.setparent(node6);
37 solution solution = new solution();
38 system.out.println(solution.getnextnode(node6).getdata());
39 }
40 }
9.用两个栈实现队列
题目：用两个栈实现一个队列。
分析：栈的结构是filo（先进后出），队列的结构是fifo（先进先出）。栈s1用于存储元素，栈s2当执行删除队列尾元素时，从s1弹出数据进入s2，再弹出s2，即实现一个队列。
1 /**
2 * 两个栈实现一个队列
3 * @author okevin
4 * @date 2019/6/3
5 **/
6 public class myqueue<t> {
7 private stack<t> s1 = new stack<>();
8 private stack<t> s2 = new stack<>();
9
10 /**
11 * 从队尾添加元素
12 * @param t 元素
13 * @return 添加的数据
14 */
15 public t appendtail(t t) {
16 s1.push(t);
17 return t;
18 }
19
20 /**
21 * 对队头删除元素
22 * @return 删除的元素
23 */
24 public t deletetail() {
25 if (s1.empty() && s2.empty()) {
26 return null;
27 }
28 if (s2.empty()) {
29 while (!s1.empty()) {
30 s2.push(s1.pop());
31 }
32 }
33 t t = s2.pop();
34 return t;
35 }
36 }
10.斐波那契数列
题目：求斐波那契数列的第n项。
解法一：递归
1 /**
2 * 求斐波那契数列的第n项
3 * @author okevin
4 * @date 2019/6/3
5 **/
6 public class solution1 {
7
8 public integer fibonacci(integer n) {
9 if (n.equals(0)) {
10 return 0;
11 }
12 if (n.equals(1)) {
13 return 1;
14 }
15 return fibonacci(n - 1) + fibonacci(n - 2);
16 }
17 }
优点：简单易懂
缺点：如果递归调用太深，容易导致栈溢出。并且节点有重复计算，导致效率不高。
解法二：循环
1 /**
2 * 求斐波那契数列的第n项
3 * @author okevin
4 * @date 2019/6/3
5 **/
6 public class solution2 {
7
8 public integer fibonacci(integer n) {
9 if (n.equals(0)) {
10 return 0;
11 }
12 if (n.equals(1)) {
13 return 1;
14 }
15 integer first = 0;
16 integer second = 1;
17 integer result = first + second;
18 for (int i = 2; i <= n; i++) {
19 result = first + second;
20 first = second;
21 second = result;
22 }
23 return result;
24 }
25 }
通过循环计算斐波那契数列能避免重复计算，且不存在调用栈过深的问题。
11. 旋转数组的最小数字
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增的数组的一个旋转，输出旋转数组的最小元素。例如，数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
*题中本意是希望能找到数组中的最小数字，直接暴力解法遍历即可。
引子：通过“二分查找”算法查找有序数组中的数字。
二分查找有序数组是否存在数字
1 /**
2 * 二分查找有序数组中的数字
3 * @author okevin
4 * @date 2019/6/3
5 **/
6 public class binarysearch {
7
8 public boolean find(integer[] array, integer target) {
9 integer start = 0;
10 integer end = array.length - 1;
11 return partition(array, start, end, target);
12 }
13
14 private boolean partition(integer[] array, integer start, integer end, integer target) {
15 if (target < array[start] || target > array[end] || start > end) {
16 return false;
17 }
18
19 int middle = (end + start) / 2;
20
21 if (target > array[middle]) {
22 return partition(array, middle + 1, end, target);
23 } else if (target < array[middle]) {
24 return partition(array, start, middle - 1, target);
25 } else {
26 return true;
27 }
28 }
29 }
利用二分法思想查找旋转数组中的最小数字，注意当出现原始数组为：{0,1,1,1,1}时，{1,1,1,0,1}和{1,0,1,1,1}均是旋转数组，这两种情况left=middle=right都是1，不能区别，此时只能按照顺序查找的方式。
1 /**
2 * 找到旋转数组中的最小值
3 * @author okevin
4 * @date 2019/6/3
5 **/
6 public class solution {
7
8 public integer find(integer[] array) {
9 if (array.length == 0) {
10 return -1;
11 }
12 int left = 0;
13 int right = array.length - 1;
14 int middle = 0;
15 while (array[left] >= array[right]) {
16 if (right - left == 1) {
17 middle = right;
18 break;
19 }
20 middle = (left + right) / 2;
21 if (array[left].equals(array[right]) && array[left].equals(array[middle])) {
22 return min(array, left, right);
23 }
24 if (array[middle] >= array[left]) {
25 left = middle;
26 } else {
27 right = middle;
28 }
29 }
30 return array[middle];
31 }
32
33 /**
34 * 当出现原始数组为：{0,1,1,1,1}时，{1,1,1,0,1}和{1,0,1,1,1}均是旋转数组，这两种情况left=middle=right都是1，不能区别
35 * @param array 数组
36 * @param left 起始
37 * @param right 结束
38 * @return
39 */
40 private integer min(integer[] array, int left, int right) {
41 int min = array[left];
42 for (int i = left + 1; i < right; i++) {
43 if (array[i] < min) {
44 min = array[i];
45 }
46 }
47 return min;
48 }
49 }
本文例子完整源码地址：https://github.com/yu-linfeng/blogrepositories/tree/master/repositories/sword
持续更新，敬请关注公众号:coderbuff，回复关键字“sword”获取相关电子书。
这是一个能给程序员加buff的公众号 （coderbuff）