【好书推荐】《剑指Offer》之硬技能（编程题7~11）
本文例子完整源码地址：https://github.com/yu-linfeng/BlogRepositories/tree/master/repositories/sword
《【好书推荐】《剑指Offer》之软技能》
《【好书推荐】《剑指Offer》之硬技能（编程题1~6）》
持续更新，敬请关注公众号: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 }
View Code
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
《【好书推荐】《剑指Offer》之软技能》
《【好书推荐】《剑指Offer》之硬技能（编程题1~6）》
持续更新，敬请关注公众号:coderbuff，回复关键字“sword”获取相关电子书。
这是一个能给程序员加buff的公众号 （CoderBuff）
相关文章