本文例子完整源码地址:https://github.com/yu-linfeng/BlogRepositories/tree/master/repositories/sword
持续更新,敬请关注公众号:coderbuff,回复关键字“sword”获取相关电子书。
7.重建二叉树
定义二叉树节点
/**
* 二叉树节点
* @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());
}
}
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
持续更新,敬请关注公众号:coderbuff,回复关键字“sword”获取相关电子书。
这是一个能给程序员加buff的公众号 (CoderBuff)