本文例子完整源码地址: 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}.
定义二叉树节点
- /**
- * 二叉树节点
- * @author OKevin
- * @date 2019/5/30
- **/
- public class Node<T> {
- /**
- * 左孩子
- */
- private Node left;
- /**
- * 右孩子
- */
- private Node right;
- /**
- * 值域
- */
- private T data;
- public Node() {
- }
- public Node(T data) {
- this.data = data;
- }
- // 省略 getter/setter 方法
- }
解法一: 递归
- /**
- * 根据前序遍历序列和中序遍历序列重建二叉树
- * @author OKevin
- * @date 2019/5/30
- **/
- public class Solution {
- public Node<Integer> buildBinaryTree(Integer[] preorder, Integer[] inorder) {
- if (preorder.length == 0 || inorder.length == 0) {
- return null;
- }
- Node<Integer> root = new Node<>(preorder[0]);
- int index = search(0, inorder, root.getData());
- root.setLeft(buildBinaryTree(Arrays.copyOfRange(preorder, 1, index + 1), Arrays.copyOfRange(inorder, 0, index)));
- root.setRight(buildBinaryTree(Arrays.copyOfRange(preorder, index + 1, preorder.length), Arrays.copyOfRange(inorder, index + 1, inorder.length)));
- return root;
- }
- /**
- * 在中序遍历的序列中查询根节点所在的位置
- * @param start 开始查找的下标
- * @param inorder 中序遍历序列
- * @param rootData 根节点值
- * @return 节点值在中序遍历序列中的下标位置
- */
- private int search(int start, Integer[] inorder, Integer rootData) {
- for (; start <inorder.length; start++) {
- if (rootData.equals(inorder[start])) {
- return start;
- }
- }
- return -1;
- }
- }
二叉树的遍历一共分为: 前序遍历, 中序遍历和后序遍历
前序遍历遍历顺序为: 根节点 ->左节点 ->右节点
中序遍历遍历顺序为: 左节点 ->根节点 ->右节点
后序遍历遍历顺序为: 左节点 ->右节点 ->根节点
例如二叉树:
- 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 3
- *// \
- * 4 5 6
- * \ /
- * 7 8
- * @author OKevin
- * @date 2019/5/30
- **/
- public class Main {
- public static void main(String[] args) {
- Integer[] preorder = new Integer[]{1, 2, 4, 7, 3, 5, 6, 8};
- Integer[] inorder = new Integer[]{4, 7, 2, 1, 5, 3, 8, 6};
- Solution solution = new Solution();
- Node<Integer> node = solution.buildBinaryTree(preorder, inorder);
- }
- }
8. 二叉树的下一个节点
题目: 给定一颗二叉树和其中的一个节点, 如何找出中序遍历序列的下一个节点? 节点中除了两个分别指向左, 右子节点的指针, 还有一个指向父节点的指针.
分析: 熟悉二叉树中序遍历的特点. 查找节点的下一个节点, 一共有两种情况: 一, 节点有右子树, 节点的下一个节点即为右子树的最左子节点; 二, 节点没有右子树, 此时又要分为两种情况: 1, 如果节点位于父节点的左节点, 节点的下一个节点即为父节点; 2, 如果节点位于父节点的右节点, 此时向上遍历, 找到它是父节点的左节点.
节点定义
- /**
- * 二叉树节点定义
- * @author OKevin
- * @date 2019/6/3
- **/
- public class Node<T> {
- /**
- * 值域
- */
- private T data;
- /**
- * 左节点
- */
- private Node<T> left;
- /**
- * 右节点
- */
- private Node<T> right;
- /**
- * 父节点
- */
- private Node<T> parent;
- public Node() {
- }
- public Node(T data) {
- this.data = data;
- }
- // 省略 getter/setter 方法
- }
中序遍历情况下, 查找二叉树节点的下一个节点
- /**
- * 中序遍历情况下, 查找节点的下一个节点
- * @author OKevin
- * @date 2019/6/3
- **/
- public class Solution {
- public Node getNextNode(Node<Integer> head) {
- if (head == null) {
- return null;
- }
- Node<Integer> p = head;
- // 第一种情况, 节点有右子树. 节点右子树的最左子节点即为节点中序遍历的下一个节点
- if (p.getRight() != null) {
- p = p.getRight();
- while (p.getLeft() != null) {
- p = p.getLeft();
- }
- return p;
- }
- // 第二种情况, 节点没有右子树. 仍然有两种情况: 一, 节点位于父节点的左节点, 此时父节点即为节点中序遍历的下一个节点; 二, 节点位于父节点的右节点, 此时一直向上查找, 直到是它父节点的左节点
- while (p.getParent() != null) {
- if (p == p.getParent().getLeft()) {
- return p.getParent();
- }
- p = p.getParent();
- }
- return null;
- }
- }
测试程序
- /**
- * 1
- */ \
- * 2 3
- *// \
- * 4 5 6
- * \ /
- * 7 8
* 中序遍历序列: 4,7,2,1,5,3,8,6
- * @author OKevin
- * @date 2019/6/3
- **/
- public class Main {
- public static void main(String[] args) {
- Node<Integer> node1 = new Node<>(1);
- Node<Integer> node2 = new Node<>(2);
- Node<Integer> node3 = new Node<>(3);
- Node<Integer> node4 = new Node<>(4);
- Node<Integer> node5 = new Node<>(5);
- Node<Integer> node6 = new Node<>(6);
- Node<Integer> node7 = new Node<>(7);
- Node<Integer> node8 = new Node<>(8);
- node1.setLeft(node2);
- node1.setRight(node3);
- node2.setLeft(node4);
- node2.setParent(node1);
- node3.setLeft(node5);
- node3.setRight(node6);
- node3.setParent(node1);
- node4.setRight(node7);
- node4.setParent(node2);
- node5.setParent(node3);
- node6.setLeft(node8);
- node6.setParent(node3);
- node7.setParent(node4);
- node8.setParent(node6);
- Solution solution = new Solution();
- System.out.println(solution.getNextNode(node6).getData());
- }
- }
- View Code
9. 用两个栈实现队列
题目: 用两个栈实现一个队列.
分析: 栈的结构是 FILO(先进后出), 队列的结构是 FIFO(先进先出). 栈 s1 用于存储元素, 栈 s2 当执行删除队列尾元素时, 从 s1 弹出数据进入 s2, 再弹出 s2, 即实现一个队列.
- /**
- * 两个栈实现一个队列
- * @author OKevin
- * @date 2019/6/3
- **/
- public class MyQueue<T> {
- private Stack<T> s1 = new Stack<>();
- private Stack<T> s2 = new Stack<>();
- /**
- * 从队尾添加元素
- * @param t 元素
- * @return 添加的数据
- */
- public T appendTail(T t) {
- s1.push(t);
- return t;
- }
- /**
- * 对队头删除元素
- * @return 删除的元素
- */
- public T deleteTail() {
- if (s1.empty() && s2.empty()) {
- return null;
- }
- if (s2.empty()) {
- while (!s1.empty()) {
- s2.push(s1.pop());
- }
- }
- T t = s2.pop();
- return t;
- }
- }
10. 斐波那契数列
题目: 求斐波那契数列的第 n 项.
解法一: 递归
- /**
- * 求斐波那契数列的第 n 项
- * @author OKevin
- * @date 2019/6/3
- **/
- public class Solution1 {
- public Integer fibonacci(Integer n) {
- if (n.equals(0)) {
- return 0;
- }
- if (n.equals(1)) {
- return 1;
- }
- return fibonacci(n - 1) + fibonacci(n - 2);
- }
- }
优点: 简单易懂
缺点: 如果递归调用太深, 容易导致栈溢出. 并且节点有重复计算, 导致效率不高.
解法二: 循环
- /**
- * 求斐波那契数列的第 n 项
- * @author OKevin
- * @date 2019/6/3
- **/
- public class Solution2 {
- public Integer fibonacci(Integer n) {
- if (n.equals(0)) {
- return 0;
- }
- if (n.equals(1)) {
- return 1;
- }
- Integer first = 0;
- Integer second = 1;
- Integer result = first + second;
- for (int i = 2; i <= n; i++) {
- result = first + second;
- first = second;
- second = result;
- }
- return result;
- }
- }
通过循环计算斐波那契数列能避免重复计算, 且不存在调用栈过深的问题.
11. 旋转数组的最小数字
题目: 把一个数组最开始的若干个元素搬到数组的末尾, 我们称之为数组的旋转. 输入一个递增的数组的一个旋转, 输出旋转数组的最小元素. 例如, 数组 {3,4,5,1,2} 为{1,2,3,4,5}的一个旋转, 该数组的最小值为 1.
* 题中本意是希望能找到数组中的最小数字, 直接暴力解法遍历即可.
引子: 通过 "二分查找" 算法查找有序数组中的数字.
二分查找有序数组是否存在数字
- /**
- * 二分查找有序数组中的数字
- * @author OKevin
- * @date 2019/6/3
- **/
- public class BinarySearch {
- public boolean find(Integer[] array, Integer target) {
- Integer start = 0;
- Integer end = array.length - 1;
- return partition(array, start, end, target);
- }
- private boolean partition(Integer[] array, Integer start, Integer end, Integer target) {
- if (target <array[start] || target> array[end] || start> end) {
- return false;
- }
- int middle = (end + start) / 2;
- if (target> array[middle]) {
- return partition(array, middle + 1, end, target);
- } else if (target <array[middle]) {
- return partition(array, start, middle - 1, target);
- } else {
- return true;
- }
- }
- }
利用二分法思想查找旋转数组中的最小数字, 注意当出现原始数组为:{0,1,1,1,1}时,{1,1,1,0,1}和 {1,0,1,1,1} 均是旋转数组, 这两种情况 left=middle=right 都是 1, 不能区别, 此时只能按照顺序查找的方式.
- /**
- * 找到旋转数组中的最小值
- * @author OKevin
- * @date 2019/6/3
- **/
- public class Solution {
- public Integer find(Integer[] array) {
- if (array.length == 0) {
- return -1;
- }
- int left = 0;
- int right = array.length - 1;
- int middle = 0;
- while (array[left]>= array[right]) {
- if (right - left == 1) {
- middle = right;
- break;
- }
- middle = (left + right) / 2;
- if (array[left].equals(array[right]) && array[left].equals(array[middle])) {
- return min(array, left, right);
- }
- if (array[middle]>= array[left]) {
- left = middle;
- } else {
- right = middle;
- }
- }
- return array[middle];
- }
- /**
- * 当出现原始数组为:{0,1,1,1,1}时,{1,1,1,0,1}和 {1,0,1,1,1} 均是旋转数组, 这两种情况 left=middle=right 都是 1, 不能区别
- * @param array 数组
- * @param left 起始
- * @param right 结束
- * @return
- */
- private Integer min(Integer[] array, int left, int right) {
- int min = array[left];
- for (int i = left + 1; i < right; i++) {
- if (array[i] < min) {
- min = array[i];
- }
- }
- return min;
- }
- }
本文例子完整源码地址: https://github.com/yu-linfeng/BlogRepositories/tree/master/repositories/sword
《[好书推荐] 《剑指 Offer》之软技能》
《[好书推荐] 《剑指 Offer》之硬技能(编程题 1~6)》
持续更新, 敬请关注公众号: coderbuff, 回复关键字 "sword" 获取相关电子书.
这是一个能给程序员加 buff 的公众号 (CoderBuff)
来源: https://www.cnblogs.com/yulinfeng/p/11001305.html