1. 队列
1.1 概述
计算机科学中，queue 是以顺序的方式维护的一组数据集合，在一端添加数据，从另一端移除数据。习惯来说，添加的一端称为尾，移除的一端称为头，就如同生活中的排队买商品
定义一个简化的队列接口：
/**
* 队列接口
* @param <E> 队列中元素类型
*/
public interface Queue<E> {
/**
* 向队列尾插入值. 有的习惯命名为 enqueue
*
* @param value 待插入值
* @return 插入成功返回 true, 插入失败返回 false
*/
boolean offer(E value);
/**
* 从对列头获取值, 并移除. 有的习惯命名为 dequeue
*
* @return 如果队列非空返回对头值, 否则返回 null
*/
E poll();
/**
* 从对列头获取值, 不移除
*
* @return 如果队列非空返回对头值, 否则返回 null
*/
E peek();
/**
* 检查队列是否为空
*
* @return 空返回 true, 否则返回 false
*/
boolean isEmpty();
/**
* 检查队列是否已满
*
* @return 满返回 true, 否则返回 false
*/
boolean isFull();
}
以下两种实现方法对应：
1.2 链表实现
下面以单向环形带哨兵链表方式来实现队列
/**
* 基于单向环形链表实现
* @param <E> 队列中元素类型
*/
public class LinkedListQueue<E>
implements Queue<E>, Iterable<E> {
// 节点类
private static class Node<E> {
E value;
Node<E> next;
public Node(E value, Node<E> next) {
this.value = value;
this.next = next;
}
}
// 头结点（指针）
private final Node<E> head = new Node<>(null, null);
// 尾结点（指针）
private Node<E> tail = head;
int size = 0; // 节点数
private int capacity = Integer.MAX_VALUE; // 容量
// 有参和无参构造方法内重复的代码=========
{
tail.next = head;
}
public LinkedListQueue() {
}
public LinkedListQueue(int capacity) {
this.capacity = capacity;
}
/**
* 尾部加入
* @param value 待插入值
* @return
*/
@Override
public boolean offer(E value) {
if (isFull()) {
return false;
}
Node<E> added = new Node<>(value, head); // 新节点（最尾部）的next指回head头
tail.next = added; // 原来的尾节点（原来的最后一个节点） 指向 新节点
tail = added; // 新节点 成为 新尾巴
size++;
return true;
}
@Override
public E poll() {
if (isEmpty()) {
return null;
}
Node<E> first = head.next;
head.next = first.next;
if (first == tail) { // 如果被移除的节点是 最后一个结点
tail = head;
}
size--;
return first.value;
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return head.next.value;
}
@Override
public boolean isEmpty() {
return head == tail;
}
@Override
public boolean isFull() {
return size == capacity;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
Node<E> p = head.next; // head 为哨兵
@Override
public boolean hasNext() {
return p != head; // 不是 p != tail，因为tail的值也要输出
}
@Override
public E next() {
E value = p.value;
p = p.next;
return value;
}
};
}
@Override
public String toString() {
StringJoiner sj = new StringJoiner(",");
for (E e : this) {
sj.add(e.toString());
}
return sj.toString();
}
}
1.3 环形数组实现
好处
- 对比普通数组，起点和终点更为自由，不用考虑数据移动
- “环”意味着不会存在【越界】问题
- 数组性能更佳
- 环形数组比较适合实现有界队列、RingBuffer 等
下标计算
例如，数组长度是 5，当前位置是 索引3 ，向前走 2 步，此时下标为 (3 + 2) % 5 = 0
- cur 当前指针位置
- step 前进步数
- length 数组长度
注意：
- 如果 step = 1，也就是一次走一步，可以在 >= length 时重置为 0 即可
判断空
开始时，数组长度为5，都没有存放元素，头指针和尾指针都指向索引0，插入一个元素后，尾指针向后移动一个。移除一个元素后，头指针则向后移动一位。
如果头尾指针指向同一个位置，那么说明队列为空。
判断满
最后一个位置用于存储尾指针，避免添加元素后后移与头指针重合，（重合判断为空）。
(tail+1) % 5=head
方法1：
/**
* 仅用 head, tail 判断空满, head, tail 即为索引值, tail 停下来的位置不存储元素
*
* @param <E> 队列中元素类型
*/
public class ArrayQueue1<E> implements Queue<E>, Iterable<E> {
private final E[] array;
private int head = 0; // 索引位置
private int tail = 0; // tail不指向数据
@SuppressWarnings("all")
public ArrayQueue1(int capacity) {
array = (E[]) new Object[capacity + 1]; // 由于尾指针需要一格存储，所以实际容量要+1
}
@Override
public boolean offer(E value) {
if (isFull()) {
return false;
}
array[tail] = value;
// 假如实际容量为4，实际长度为5，[0 1 2 3 4 -> 0] ），若tail指针原来指向4，再移动一位则需要重置为0
tail = (tail + 1) % array.length;
return true;
}
@Override
public E poll() {
if (isEmpty()) {
return null;
}
E value = array[head];
array[head] = null; // help GC
head = (head + 1) % array.length;
return value;
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return array[head];
}
@Override
public boolean isEmpty() {
return head == tail;
}
@Override
public boolean isFull() {
return (tail + 1) % array.length == head;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int p = head;
@Override
public boolean hasNext() {
return p != tail; // tail不指向数据
}
@Override
public E next() {
E value = array[p];
p = (p + 1) % array.length;
return value;
}
};
}
}
方法2：
上述代码，因为要判断空或满，所以tail指针指向的位置不存储。
也可以引入size来判断。
部分代码如下：
private int size = 0; // 元素个数
@SuppressWarnings("all")
public ArrayQueue2(int capacity) {
array = (E[]) new Object[capacity];
}
// offer方法添加 size++;
// poll方法添加 size--;
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == array.length;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int p = head;
int count = 0; // 遍历时 计数器从0到size-1
@Override
public boolean hasNext() {
return count < size;
}
@Override
public E next() {
E value = array[p];
p = (p + 1) % array.length;
count++;
return value;
}
};
}
方法3，前置知识：
二进制求商和余数：
要直接得到余数（后n为），可以将被除数进行按位与操作，如果要得到后三位，可以与前面五位是0，后面三位是1的数字，即数字7。
示例2：
判断二进制数：
取一个数最近的二进制数（大于原来的数）：
移位求取：
c--;
c |= c >> 1;
c |= c >> 2;
c |= c >> 4;
c |= c >> 8;
c |= c >> 16;
c++;
乍一看可能有些蒙，我们随便取个值来分析一下，——就【827】了（1100111011）。
1100111011 -1 temp： 1100111010
0110011101 temp>>1
1110111111 temp |= temp: 1110111111 此步主要为了保证第一位一定是1，如果所有位都为1，则已经是结果了
0011101111 temp >>2
11111111111 temp |= temp:1111111111 这样就保证了前两位一定是1，以此类推（虽然已经满足了）保证所有位为1
（右移1位后，再右移2位，就累计右移了3位，所以下一步是移动4位）
。。。。。。
但是这样并不是我们想要的结果，因为2的次方数【只】有高位为1，所以我们只需要再+1，就ok了。（这也是前面为什么要减一的原因）。
示例参考链接：https://blog.csdn.net/qq_41786131/article/details/103150710
判断空、满方法3
- head 和 tail 不断递增，用到索引时，再用它们进行计算，两个问题
- 如何保证 head 和 tail 自增超过正整数最大值的正确性。
Integer.toUnsignedLong()，转为long形 - 如何让取模运算性能更高
- 如何保证 head 和 tail 自增超过正整数最大值的正确性。
- 答案：让 capacity 为 2 的幂
/**
* 仅用 head, tail 判断空满, head, tail 需要换算成索引值
*
* @param <E> 队列中元素类型
*/
public class ArrayQueue3<E> implements Queue<E>, Iterable<E> {
/*
求模运算：
- 如果除数是 2 的 n 次方
- 那么被除数的后 n 位即为余数 (模)
- 求被除数的后 n 位方法： 与 2^n-1 按位与
*/
private final E[] array;
int head = 0;
int tail = 0;
@SuppressWarnings("all")
public ArrayQueue3(int c) {
// 传递数组长度不为2的n次方
// 1. 抛异常
/*if ((capacity & capacity - 1) != 0) {
throw new IllegalArgumentException("capacity 必须是2的幂");
}*/
// 2. 改成 2^n 13 -> 16 22 -> 32
c -= 1;
c |= c >> 1;
c |= c >> 2;
c |= c >> 4;
c |= c >> 8;
c |= c >> 16;
c += 1;
array = (E[]) new Object[c];
}
/*
head = 0
tail = 3 % 3 = 0
capacity=3
0 1 2
d b c
*/
@Override
public boolean offer(E value) {
if (isFull()) {
return false;
}
// tail需要时取模，tail一直++
// array[(int) (Integer.toUnsignedLong(tail) % array.length)] = value;
// 按位与取余数要的是后几位，与前面符号位无关
array[tail & (array.length - 1)] = value;
tail++;
return true;
}
@Override
public E poll() {
if (isEmpty()) {
return null;
}
// E value = array[(int) Integer.toUnsignedLong(head) % array.length];
int idx = head & (array.length - 1);
E value = array[idx];
array[idx] = null; // help GC
head++;
return value;
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return array[head & (array.length - 1)];
}
@Override
public boolean isEmpty() {
return head == tail;
}
@Override
public boolean isFull() {
// 即使tail超过Integer最大值，在减去数据后，依然能输出正确结果，前提是数组长度不能超过Interger最大值
return tail - head == array.length;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int p = head;
@Override
public boolean hasNext() {
return p != tail;
}
@Override
public E next() {
// E value = array[(int) Integer.toUnsignedLong(p) % array.length];
E value = array[p & (array.length - 1)];
p++;
return value;
}
};
}
// 验证 使用位运算下，tail - head 不会有问题
// origin code: TestArrayQueue3.java
@Test
public void test2() {
int head = 2147483640;
int tail = 2147483647; // 最大值
tail += 5;
System.out.println(tail); // -2147483644
System.out.println(tail - head); // 12
}
public static void main(String[] args) {
// 验证 Integer.toUnsignedLong() 下，tail - head 不会有问题
System.out.println(Integer.MAX_VALUE);
// tail 已经自增为负数
int head = 1_900_000_000;
int tail = 2_100_000_000;
for (int i = 0; i < 20; i++) {
tail += 100_000_000;
System.out.println(Integer.toUnsignedLong(tail) + " " + Integer.toUnsignedLong(head) + " " + (tail - head));
}
// 最后一次显示负数是因为 tail-head 4100000000-1900000000=2200000000 也超过了正整数最大值,而实际这种情况不可能发生(数组最大长度为正整数最大值)
// head 和 tail 都成了负数
System.out.println("===========================");
head = -20 9496 7296; // 2200000000
tail = -20 9496 7296; // 2200000000
for (int i = 0; i < 20; i++) {
tail += 100_000_000;
System.out.println(Integer.toUnsignedLong(tail) + " " + Integer.toUnsignedLong(head) + " " + (tail - head));
}
// 求离c最近，比c大的 2^n (方法1)
int c = 32;
/*
2^4 = 16
2^4.? = 30
2^5 = 32
(int)log2(30) + 1
2
log2(x) = log10(x) / log10(2)
1 左移一位
10 2^1
100 2^2
1000 2^3
*/
// 先-1，避免如果传过来额数刚好是 2的n次方，导致+1后 数据变大。
/*int n = (int) (Math.log10(c-1) / Math.log10(2)) + 1;
System.out.println(n);
// 左移5位，即为2的5次方
System.out.println(1 << n);*/
// 求离c最近，比c大的 2^n (方法2) 逻辑或
c--;
c |= c >> 1;
c |= c >> 2;
c |= c >> 4;
c |= c >> 8;
c |= c >> 16;
c++;
System.out.println(c);
}
}
1.4 例题
1.4.1 二叉树的层序遍历
本题为后端高频面试题，被收录于《热招技术岗上岸指南》
给你二叉树的根节点
root，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
输入：root = [1]
输出：[[1]]
输入：root = []
输出：[]
/**
* Definition for a binary tree node.
*/
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
思路，使用队列，头入列，从队列弹出一个元素，判断其有无左右节点，加入队列。
/**
* 二叉树层序遍历
*/
public class E01Leetcode102 {
/*
[
[1]
[2,3]
[4,5,6,7]
]
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>(); // 外层集合
if (root == null) {
return result;
}
// 或者使用JDK自带 Queue 及 实现类 LinkedList
// Queue<TreeNode> queue = new LinkedList<TreeNode>();
LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();
queue.offer(root);
int c1 = 1; // 当前层节点数
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>(); // 保存每一层结果
int c2 = 0; // 下一层节点数
for (int i = 0; i < c1; i++) {
TreeNode n = queue.poll();
level.add(n.val);
if (n.left != null) {
queue.offer(n.left);
c2++;
}
if (n.right != null) {
queue.offer(n.right);
c2++;
}
}
result.add(level);
c1 = c2;
}
return result;
}
/*
1
/ \
2 3
/\ /\
4 5 6 7
头 [] 尾
1 2 3 4 5 6 7
*/
public static void main(String[] args) {
TreeNode root = new TreeNode(
new TreeNode(
new TreeNode(4),
2,
new TreeNode(5)
),
1,
new TreeNode(
new TreeNode(6),
3,
new TreeNode(7)
)
);
List<List<Integer>> lists = new E01Leetcode102().levelOrder(root);
for (List<Integer> list : lists) {
System.out.println(list);
}
/*
LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();
queue.offer(root);
int c1 = 1; // 当前层节点数
while (!queue.isEmpty()) {
int c2 = 0; // 下一层节点数
for (int i = 0; i < c1; i++) {
TreeNode n = queue.poll();
System.out.print(n + " ");
if (n.left != null) {
queue.offer(n.left);
c2++; // 当前层有左孩子，那到下一层遍历时要遍历到 +1
}
if (n.right != null) {
queue.offer(n.right);
c2++;
}
}
System.out.println();
c1 = c2; // 遍历到下一层是，将下一层节点数传递到 c1当前层节点数
}
*/
}
}
力扣官方解法，判断节点数直接使用 LinkedList 的实例方法 queue.size();
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) {
return ret; // 返回空数组
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<Integer>();
int currentLevelSize = queue.size();
for (int i = 1; i <= currentLevelSize; ++i) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
ret.add(level);
}
return ret;
}
}
2. 栈
2.1 概述
计算机科学中，stack 是一种线性的数据结构，只能在其一端添加数据和移除数据。习惯来说，这一端称之为栈顶，另一端不能操作数据的称之为栈底，就如同生活中的一摞书
接口定义：
public interface Stack<E> {
/**
* 向栈顶压入元素
*
* @param value 待压入值
* @return 压入成功返回 true, 否则返回 false
*/
boolean push(E value);
/**
* 从栈顶弹出元素
*
* @return 栈非空返回栈顶元素, 栈为空返回 null
*/
// 实际的stack.pop()，空的时候会报 java.util.EmptyStackException
E pop();
/**
* 返回栈顶元素, 不弹出
*
* @return 栈非空返回栈顶元素, 栈为空返回 null
*/
E peek();
/**
* 判断栈是否为空
*
* @return 空返回 true, 否则返回 false
*/
boolean isEmpty();
/**
* 判断栈是否已满
*
* @return 满返回 true, 否则返回 false
*/
boolean isFull();
}
2.2 基于链表实现
public class LinkedListStack<E> implements Stack<E>, Iterable<E> {
private int capacity = Integer.MAX_VALUE;
private int size;
private final Node<E> head = new Node<>(null, null);
public LinkedListStack() {
}
public LinkedListStack(int capacity) {
this.capacity = capacity;
}
/*
head -> 2 -> 1 -> null
*/
@Override
public boolean push(E value) {
if (isFull()) {
return false;
}
head.next = new Node<>(value, head.next);
size++;
return true;
}
/*
head -> 2 -> 1 -> null
*/
@Override
public E pop() {
if (isEmpty()) {
return null;
}
Node<E> first = head.next;
head.next = first.next;
size--;
return first.value;
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return head.next.value;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == capacity;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
Node<E> p = head.next;
@Override
public boolean hasNext() {
return p != null;
}
@Override
public E next() {
E value = p.value;
p = p.next;
return value;
}
};
}
static class Node<E> {
E value;
Node<E> next;
public Node(E value, Node<E> next) {
this.value = value;
this.next = next;
}
}
@Override
public String toString() {
StringJoiner sj = new StringJoiner(",");
for (E e : this) {
sj.add(e.toString());
}
return sj.toString();
}
}
2.3 数组实现
底 顶
0 1 2 3
public class ArrayStack<E> implements Stack<E>, Iterable<E> {
private final E[] array;
private int top; // 栈顶指针索引
@SuppressWarnings("all")
public ArrayStack(int capacity) {
this.array = (E[]) new Object[capacity];
}
@Override
public boolean push(E value) {
if (isFull()) {
return false;
}
array[top++] = value;
return true;
}
@Override
public E pop() {
if (isEmpty()) {
return null;
}
E e = array[--top];
array[top] = null; // help GC
return e;
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return array[top - 1];
}
@Override
public boolean isEmpty() {
return top == 0;
}
@Override
public boolean isFull() {
return top == array.length;
}
/*
底 顶
0 1 2 3
a b c d
p
*/
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int p = top;
@Override
public boolean hasNext() {
return p > 0;
}
@Override
public E next() {
return array[--p];
}
};
}
}
2.4 应用
模拟方法调用：
public static void main(String[] args) {
System.out.println("main1");
System.out.println("main2");
method1();
method2();
System.out.println("main3");
}
public static void method1() {
System.out.println("method1");
method3();
}
public static void method2() {
System.out.println("method2");
}
public static void method3() {
System.out.println("method3");
}
main1
main2
method1
method3
method2
main3
模拟代码：
public class CPU {
static class Frame {
int exit;
public Frame(int exit) {
this.exit = exit;
}
}
static int pc = 1; // 模拟程序计数器 Program counter
static ArrayStack<Frame> stack = new ArrayStack<>(100); // 模拟方法调用栈
public static void main(String[] args) {
stack.push(new Frame(-1));
while (!stack.isEmpty()) {
switch (pc) {
case 1 -> {
System.out.println("main1");
pc++;
}
case 2 -> {
System.out.println("main2");
pc++;
}
case 3 -> {
// 原来栈中的-1还没弹出，又压入4
stack.push(new Frame(pc + 1));
pc = 100; // 跳转到100
}
case 4 -> {
// 压人 5, -1 5
stack.push(new Frame(pc + 1));
pc = 200;
}
case 5 -> {
// 弹出 -1 pc=-1, 此时stack已经清空
System.out.println("main3");
pc = stack.pop().exit;
}
case 100 -> {
System.out.println("method1");
// -1 4 101
stack.push(new Frame(pc + 1));
pc = 300; // 跳转到 300
}
case 101 -> {
pc = stack.pop().exit; // 弹出 4 pc = 4
}
case 200 -> {
System.out.println("method2");
pc = stack.pop().exit; // 弹出 5， pc = 5
}
case 300 -> {
// 弹出 101
System.out.println("method3");
pc = stack.pop().exit; // pc = 101
}
}
}
}
}
2.5 例题
2.5.1 有效括号
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号
示例：
输入：s = "()"
输出：true
输入：s = "()[]{}"
输出：true
输入：s = "(]"
输出：false
运用
java.util.stack直接解答，遇到左括号则压入push相应的右括号，遇到右括号则弹出栈顶，进行判断，如果一样则continue;雷区：String字符串如果全是左侧括号，没有右侧括号，则不会进行弹出栈顶判断的情况。因此最后return时要判断stack是否为空，空则说明全部字符完成判断。
雷区2：当stack为空时，若第一个字符为右侧括号，进行弹栈判断会报错，因此要增加判断。
字符串.length为单数，括号肯定不成配，直接false。
个人代码如下：
public boolean isValid(String s) {
if (s.length() % 2 == 1) {
return false;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
switch (c) {
case '(' -> stack.push(')');
case '{' -> stack.push('}');
case '[' -> stack.push(']');
default -> {
if (stack.empty() || !stack.pop().equals(c)) {
return false;
}
}
}
}
return stack.empty();
}
力扣官方题解：
class Solution {
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}
2.5.2 后缀表达式
两题相同：
根据 逆波兰表示法，求该后缀表达式的计算结果。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
- 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
示例：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
思路：新建一个Stack，遇到数字就压入栈中，遇到符号则弹出两个进行计算，将结果再压入栈。所有遍历后，将结果弹出。
雷点：弹出的数字是有顺序的，除了加法和乘法外。先弹出的是被减数or除数（在符号右侧的 ）。
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
switch (token) {
case "+" -> {
// 先弹出的结果，在原数组中是靠后的
Integer back = stack.pop();
Integer font = stack.pop();
stack.push(font + back);
}
case "-" -> {
Integer back = stack.pop();
Integer front = stack.pop();
stack.push(front - back);
}
case "*" -> {
Integer back = stack.pop();
Integer font = stack.pop();
stack.push(font * back);
}
case "/" -> {
Integer back = stack.pop();
Integer font = stack.pop();
stack.push(font / back);
}
default -> stack.push(Integer.parseInt(token));
}
}
// 遍历结束后的就是结果
return stack.pop();
}
Java编译后的class文件采用的就是后缀表达式
2.5.3 中缀表达式转后缀表达式
/*
思路
| |
| |
| |
_____
遇到非计算符号，直接加入字符串，遇到运算符，先压入栈
a+b ab+
a+b-c ab+c- 遇到减号，因为+-平级，从左到右，先弹出+号，-号压入栈中
a*b+c ab*c+ 遇到+号，乘号先运算弹出，+号入栈
a+b*c abc*+ 遇到优先级高的*号，*号也入栈，
a+b*c-d abc*+d- 遇到-号时，和乘号比，先出栈优先级高的*号，再出栈优先级相同的+号
(a+b)*c ab+c* 左括号也要入栈，然后+号也要入栈，所以(优先级更低，遇到右括号，将栈中左括号前的出栈，然后左括号出栈
(a+b*c-d)*e abc*+d-e* 遇到-号时，将比-号高和等于它的出栈，括号不出栈，然后-入栈
a*(b+c) abc+*
1. 遇到非运算符 直接拼串
2. 遇到 + - * /
- 它的优先级比栈顶运算符高, 入栈, 如: 栈中是 + 当前是 *
- 否则把栈里优先级 >= 它 的都出栈, 它再入栈, 如: 栈中是 +*, 当前是 -
3. 遍历完成, 栈里剩余运算符依次出栈
4. 带()
- 左括号直接入栈, 左括号优先设置为0
- 右括号就把栈里到左括号为止的所有运算符出栈
*/
代码：
package algorithms.stack;
import java.util.LinkedList;
/**
* 中缀表达式转后缀
*/
public class E03InfixToSuffix {
public static void test() {
int a = 10;
int b = 20;
int c = 5;
int d = (a + b) * c;
}
public static void main(String[] args) {
// System.out.println(infixToSuffix("a+b"));
// System.out.println(infixToSuffix("a+b-c"));
// System.out.println(infixToSuffix("a+b*c"));
// System.out.println(infixToSuffix("a*b-c"));
System.out.println(infixToSuffix("(a+b)*c"));
System.out.println(infixToSuffix("(a+b*c-d)*e"));
System.out.println(infixToSuffix("a*(b+c)"));
}
/**
* @param c 符号
* @return 返回优先级
*/
static int priority(char c) {
return switch (c) {
case '*', '/' -> 2;
case '+', '-' -> 1;
case '(' -> 0;
default -> throw new IllegalArgumentException("不合法的运算符:" + c);
};
}
static String infixToSuffix(String exp) {
LinkedList<Character> stack = new LinkedList<>();
StringBuilder sb = new StringBuilder(exp.length());
for (int i = 0; i < exp.length(); i++) {
char c = exp.charAt(i);
switch (c) {
case '*', '/', '+', '-' -> {
// 栈空直接压栈
if (stack.isEmpty()) {
stack.push(c);
} else {
// 栈顶优先级低，压入高优先级符号
if (priority(c) > priority(stack.peek())) {
stack.push(c);
} else {
// 栈不为空的情况下，把剩余的符号弹出来
while (!stack.isEmpty() && priority(stack.peek()) >= priority(c)) {
sb.append(stack.pop()); // 拼入字符串
}
stack.push(c);
}
}
}
case '(' -> {
stack.push(c);
}
case ')' -> {
while (!stack.isEmpty() && stack.peek() != '(') {
sb.append(stack.pop());
}
stack.pop(); // 弹出左括号
}
default -> {
sb.append(c);
}
}
}
// 循环结束后，弹空栈
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.toString();
}
}
2.5.4 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现
MyQueue类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false- 你 只能 使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。
示例：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：
1 <= x <= 9- 最多调用
100次push、pop、peek和empty - 假设所有操作都是有效的 （例如，一个空的队列不会调用
pop或者peek操作） - 你能否实现每个操作均摊时间复杂度为
O(1)的队列？换句话说，执行n个操作的总时间复杂度为O(n)，即使其中一个操作可能花费较长时间。
相当于两杯水，第一杯的杯底会倒到第二杯最上面，最上面的会到另一杯杯底
使用数组stack
官方解答：
方法一：双栈，思路：
将一个栈当作输入栈，用于压入
push传入的数据；另一个栈当作输出栈，用于pop和peek操作。每次
pop或peek时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。
class MyQueue {
Deque<Integer> inStack;
Deque<Integer> outStack;
public MyQueue() {
inStack = new ArrayDeque<Integer>();
outStack = new ArrayDeque<Integer>();
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
if (outStack.isEmpty()) {
in2out();
}
return outStack.pop();
}
public int peek() {
if (outStack.isEmpty()) {
in2out();
}
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
private void in2out() {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
}
复杂度分析
- 时间复杂度：
push和empty为O(1)，pop和peek为均摊O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为O(1)。- 空间复杂度：
O(n)。其中n是操作总数。对于有n次push操作的情况，队列中会有n个元素，故空间复杂度为O(n)。
解答二：（方法类似）
public class E04Leetcode232 {
/*
队列头 队列尾
b
顶 底 底 顶
s1 s2
队列尾添加
s2.push(a)
s2.push(b)
队列头移除
先把 s2 的所有元素移动到 s1
s1.pop()
*/
ArrayStack<Integer> s1 = new ArrayStack<>(100);
ArrayStack<Integer> s2 = new ArrayStack<>(100);
public void push(int x) { //向队列尾添加
s2.push(x);
}
public int pop() { // 从对列头移除
if (s1.isEmpty()) { // s1为空，将s2所有元素移除，添加到s1
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}
return s1.pop();
}
public int peek() { // 从对列头获取
if (s1.isEmpty()) {
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}
return s1.peek();
}
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
2.5.5 用队列模拟栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop和empty）。实现
MyStack类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。进阶：你能否仅用一个队列来实现栈。
思路：
两个队列：
queue1存储元素为“栈”，queue2作为辅助队列。入栈时，将元素存入queue2，此时新元素成为头，被移除时也是第一个，符合栈的后入先出。再将queue1所有元素依次出队入队移到queue2，最后queue1与queue2互换。
一个队列：引入
queue.size()，每次push时，先入队，再将原队列size个元素依次出队后重新入队，实现新元素成为队头，符合栈的后入先出。（排队时，当前面所有人排到你后面，你就是第一个）
双队列代码：
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
/** Initialize your data structure here. */
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
queue2.offer(x);
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll();
}
/** Get the top element. */
public int top() {
return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}
单队列代码：
/**
* 单队列模拟栈
* <ol>
* <li>调用 push、pop 等方法的次数最多 100</li>
* <li>每次调用 pop 和 top 都能保证栈不为空</li>
* </ol>
*/
public class E05Leetcode225 {
/*
栈顶 栈底
d c b a
队列头 队列尾
queue.offer(a)
queue.offer(b)
queue.offer(c)
push 添加
- 将新加入元素，前面的所有元素从队列头移动到队列尾，此时新元素成为队列头
pop 移除
- 直接移除队列头元素
*/
Queue<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
queue = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
int n = queue.size();
queue.offer(x);
for (int i = 0; i < n; i++) {
queue.offer(queue.poll());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.poll();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}
3. 双端队列
相似例题：641. 设计循环双端队列
3.1 概述
双端队列、队列、栈对比
| 定义 | 特点 | |
|---|---|---|
| 队列 | 一端删除（头）另一端添加（尾） | First In First Out |
| 栈 | 一端删除和添加（顶） | Last In First Out |
| 双端队列 | 两端都可以删除、添加 | |
| 优先级队列 | 优先级高者先出队 | |
| 延时队列 | 根据延时时间确定优先级 | |
| 并发非阻塞队列 | 队列空或满时不阻塞 | |
| 并发阻塞队列 | 队列空时删除阻塞、队列满时添加阻塞 |
注1：
- Java 中
LinkedList即为典型双端队列实现，不过它同时实现了Queue接口，也提供了栈的push，pop等方法注2：
- 不同语言，操作双端队列的方法命名有所不同，参见下表
操作 Java JavaScript C++ leetCode 641 尾部插入 offerLast push push_back insertLast 头部插入 offerFirst unshift push_front insertFront 尾部移除 pollLast pop pop_back deleteLast 头部移除 pollFirst shift pop_front deleteFront 尾部获取 peekLast at(-1) back getRear 头部获取 peekFirst at(0) front getFront - 吐槽一下
leetCode命名比较 low- 常见的单词还有
enqueue入队、dequeue出队
接口定义：
public interface Deque<E> {
boolean offerFirst(E e);
boolean offerLast(E e);
E pollFirst();
E pollLast();
E peekFirst();
E peekLast();
boolean isEmpty();
boolean isFull();
}
3.2 链表实现
使用双向链表，不仅要知道下一个节点也要知道上一个节点。
使用环形链表，即可以充当头，也可以充当尾。
【队列中，哨兵的下一个
next即为队列头（将被移除）】
/**
* 基于双向环形链表实现
*
* @param <E> 队列中元素类型
*/
public class LinkedListDeque<E> implements Deque<E>, Iterable<E> {
static class Node<E> {
Node<E> prev;
E value;
Node<E> next;
public Node(Node<E> prev, E value, Node<E> next) {
this.prev = prev;
this.value = value;
this.next = next;
}
}
int capacity;
int size;
Node<E> sentinel = new Node<>(null, null, null);
public LinkedListDeque(int capacity) {
this.capacity = capacity;
sentinel.next = sentinel;
sentinel.prev = sentinel;
}
@Override
public boolean offerFirst(E e) {
if (isFull()) {
return false;
}
Node<E> a = sentinel;
Node<E> b = sentinel.next;
Node<E> added = new Node<>(a, e, b);
a.next = added;
b.prev = added;
size++;
return true;
}
@Override
public boolean offerLast(E e) {
if (isFull()) {
return false;
}
Node<E> a = sentinel.prev;
Node<E> b = sentinel;
Node<E> added = new Node<>(a, e, b);
a.next = added;
b.prev = added;
size++;
return false;
}
// a b
@Override
public E pollFirst() {
if (isEmpty()) {
return null;
}
Node<E> a = sentinel;
Node<E> removed = sentinel.next;
Node<E> b = removed.next;
a.next = b;
b.prev = a;
size--;
return removed.value;
}
// a b
@Override
public E pollLast() {
if (isEmpty()) {
return null;
}
Node<E> b = sentinel;
Node<E> removed = sentinel.prev;
Node<E> a = removed.prev;
a.next = b;
b.prev = a;
size--;
return removed.value;
}
@Override
public E peekFirst() {
if (isEmpty()) {
return null;
}
return sentinel.next.value;
}
@Override
public E peekLast() {
if (isEmpty()) {
return null;
}
return sentinel.prev.value;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == capacity;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
Node<E> p = sentinel.next;
@Override
public boolean hasNext() {
return p != sentinel;
}
@Override
public E next() {
E value = p.value;
p = p.next;
return value;
}
};
}
}
3.3 数组实现
双端队列数组实现_内存释放：
基本数据类型：如int，数据清为0后，依然占用4个字节。
引用数据类型：存储的是地址值，将存储的值置为 null ，对象没有引用，会被释放。
代码实现：
/**
* 基于循环数组实现, 特点
* <ul>
* <li>tail 停下来的位置不存储, 会浪费一个位置</li>
* </ul>
*
* @param <E> 队列中元素类型
*/
public class ArrayDeque1<E> implements Deque<E>, Iterable<E> {
E[] array;
int head;
int tail;
@SuppressWarnings("all")
public ArrayDeque1(int capacity) {
array = (E[]) new Object[capacity + 1];
}
/*
h - head
t - tail
h-> h （实际时向前移，然后跑到了最后一位）
t-> t-> t
0 1 2 3
a b
c
offerLast(a) 先添加元素，然后tail++
offerLast(b)
offerFirst(c) 先 head-- 再添加元素
pollFirst() 先获取要移除的值 head++
pollLast() 先 tail-- 再获取要移除的值
head == tail 空
head ~ tail == 数组长度-1 满
*/
/*
h
t
0 1 2 3
a b
索引 增长后保持索引合法
*/
static int inc(int i, int length) {
if (i + 1 >= length) {
return 0;
}
return i + 1;
}
/*
h
t
0 1 2 3
a b
*/
static int dec(int i, int length) {
if (i - 1 < 0) {
return length - 1;
}
return i - 1;
}
@Override
public boolean offerFirst(E e) {
if (isFull()) {
return false;
}
head = dec(head, array.length);
array[head] = e;
return true;
}
@Override
public boolean offerLast(E e) {
if (isFull()) {
return false;
}
array[tail] = e;
tail = inc(tail, array.length);
return true;
}
@Override
public E pollFirst() {
if (isEmpty()) {
return null;
}
E e = array[head];
array[head] = null; // help GC
head = inc(head, array.length);
return e;
}
@Override
public E pollLast() {
if (isEmpty()) {
return null;
}
tail = dec(tail, array.length);
E e = array[tail];
array[tail] = null; // help GC
return e;
}
@Override
public E peekFirst() {
if (isEmpty()) {
return null;
}
return array[head];
}
@Override
public E peekLast() {
if (isEmpty()) {
return null;
}
return array[dec(tail, array.length)];
}
@Override
public boolean isEmpty() {
return head == tail;
}
/*
h
t
0 1 2 3
a b c
当tail>head时
3-0==array.length-1
*/
/*
h
t
0 1 2 3
c b a
tail<head
head-tail==1
*/
@Override
public boolean isFull() {
if (tail > head) {
return tail - head == array.length - 1;
} else if (tail < head) {
return head - tail == 1;
} else {
return false;
}
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int p = head;
@Override
public boolean hasNext() {
return p != tail;
}
@Override
public E next() {
E e = array[p];
p = inc(p, array.length);
return e;
}
};
}
}
3.4 例题：二叉树锯齿形遍历
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
/*
1
/ \
2 3
/\ /\
4 5 6 7
/\
8 9
依次输出：
1
3 2
4 5 6 7
9 8
*/
示例：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
输入：root = [1]
输出：[[1]]
输入：root = []
输出：[]
思路：
普通层序遍历：使用
队列z字遍历：使用双端队列，奇数层正常添加，偶数层头部添加。
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new LinkedList<List<Integer>>();
if (root == null) {
return ans;
}
Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();
nodeQueue.offer(root);
boolean isOrderLeft = true; // 奇数层， 从左到右添加
while (!nodeQueue.isEmpty()) {
Deque<Integer> levelList = new LinkedList<Integer>(); // 保存每一层结果
int size = nodeQueue.size(); // 每一层节点个数
for (int i = 0; i < size; ++i) {
TreeNode curNode = nodeQueue.poll();
if (isOrderLeft) {
levelList.offerLast(curNode.val);
} else {
levelList.offerFirst(curNode.val);
}
if (curNode.left != null) {
nodeQueue.offer(curNode.left);
}
if (curNode.right != null) {
nodeQueue.offer(curNode.right);
}
}
ans.add(new LinkedList<Integer>(levelList));
isOrderLeft = !isOrderLeft;
}
return ans;
}
}
4. 优先级队列
java.util.PriorityQueue 基于二叉小顶堆实现。
队列元素带优先级，优先级高的先出队。
接口定义：
Priority：
public interface Priority {
/**
* 返回对象的优先级, 约定数字越大, 优先级越高
* @return 优先级
*/
int priority();
}
Entry：
class Entry implements Priority {
String value;
int priority;
public Entry(int priority) {
this.priority = priority;
}
public Entry(String value, int priority) {
this.value = value;
this.priority = priority;
}
@Override
public int priority() {
return priority;
}
@Override
public String toString() {
return "(" + value + " priority=" + priority + ")";
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Entry entry = (Entry) o;
return priority == entry.priority;
}
@Override
public int hashCode() {
return priority;
}
}
优先级队列中，继承 Priority 接口后，每个元素都可以通过.priority()获取优先级。
4.1 无序数组实现
要点
- 入队保持顺序
- 出队前找到优先级最高的出队，相当于一次选择排序
package algorithms.priorityqueue;
import algorithms.queue.Queue;
/**
* 基于<b>无序数组</b>实现
*
* @param <E> 队列中元素类型, 必须实现 Priority 接口
*/
@SuppressWarnings("all")
public class PriorityQueue1<E extends Priority> implements Queue<E> {
Priority[] array;
int size;
public PriorityQueue1(int capacity) {
array = new Priority[capacity];
}
@Override // O(1)
public boolean offer(E e) {
if (isFull()) {
return false;
}
array[size++] = e;
return true;
}
// 返回优先级最高的索引值
private int selectMax() {
int max = 0;
for (int i = 1; i < size; i++) {
if (array[i].priority() > array[max].priority()) {
max = i;
}
}
return max;
}
@Override // O(n)
public E poll() {
if (isEmpty()) {
return null;
}
int max = selectMax();
E e = (E) array[max];
remove(max);
return e;
}
private void remove(int index) {
if (index < size - 1) {
// 移动
System.arraycopy(array, index + 1,
array, index, size - 1 - index);
}
array[--size] = null; // help GC
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
int max = selectMax();
return (E) array[max];
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == array.length;
}
}
4.2 有序数组实现
要点
- 入队后排好序，优先级最高的排列在尾部
- 出队只需删除尾部元素即可
package algorithms.priorityqueue;
import algorithms.queue.Queue;
/**
* 基于<b>有序数组</b>实现
*
* @param <E> 队列中元素类型, 必须实现 Priority 接口
*/
@SuppressWarnings("all")
public class PriorityQueue2<E extends Priority> implements Queue<E> {
Priority[] array;
int size;
public PriorityQueue2(int capacity) {
array = new Priority[capacity];
}
@Override
public boolean offer(E e) {
if (isFull()) {
return false;
}
insert(e);
size++;
return true;
}
// O(n)
/**
* 从优先级最大处（队尾）开始比较，
* 找到优先级低于e的索引，每次和一个值比较后，同时将该值向后移（拷贝）
* 插入位置即在其（比e优先级低的值的）后面，赋值（覆盖）
* （isFull时无法插入，需要保证有一个空位可以移动）
* @param e
*/
private void insert(E e) {
int i = size - 1;
while (i >= 0 && array[i].priority() > e.priority()) {
array[i + 1] = array[i];
i--;
}
array[i + 1] = e; // -1 + 1 = 0，边界条件可行
}
// O(1)
@Override
public E poll() {
if (isEmpty()) {
return null;
}
E e = (E) array[size - 1];
array[--size] = null; // help GC
return e;
}
/**
* 优先级最高在数组尾部
* @return
*/
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return (E) array[size - 1];
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == array.length;
}
}
4.3 堆实现
计算机科学中，堆是一种基于树的数据结构，通常用完全二叉树实现。堆的特性如下
- 在大顶堆中，任意节点 C 与它的父节点 P 符合
P.value \geq C.value - 而小顶堆中，任意节点 C 与它的父节点 P 符合
P.value \leq C.value - 最顶层的节点（没有父亲）称之为 root 根节点
In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node
例1 - 满二叉树（Full Binary Tree）特点：每一层都是填满的
例2 - 完全二叉树（Complete Binary Tree）特点：最后一层可能未填满，靠左对齐
例3 - 大顶堆
例4 - 小顶堆
完全二叉树可以使用数组来表示：
特征
- 如果从索引 0 开始存储节点数据
- 节点
i的父节点为floor((i-1)/2)，当i>0时 - 节点
i的左子节点为2i+1，右子节点为2i+2，当然它们得< size
- 节点
- 如果从索引 1 开始存储节点数据
- 节点
i的父节点为floor(i/2)，当i > 1时 - 节点
i的左子节点为2i，右子节点为2i+1，同样得< size
- 节点
4.3.1 大顶堆实现
代码：
package algorithms.priorityqueue;
import algorithms.queue.Queue;
/**
* 基于<b>大顶堆</b>实现
* @param <E> 队列中元素类型, 必须实现 Priority 接口
*/
@SuppressWarnings("all")
public class PriorityQueue4<E extends Priority> implements Queue<E> {
Priority[] array;
int size;
public PriorityQueue4(int capacity) {
array = new Priority[capacity];
}
/*
1. 入堆新元素, 加入到数组末尾 (索引位置 child)
2. 不断比较新加元素与它父节点(parent)优先级 (上浮)
- 如果父节点优先级低, 则向下移动, 并找到下一个 parent
- 直至父节点优先级更高或 child==0 为止
*/
@Override
public boolean offer(E offered) {
if (isFull()) {
return false;
}
int child = size++;
int parent = (child - 1) / 2;
// child = 0也为终点
while (child > 0 && offered.priority() > array[parent].priority()) {
array[child] = array[parent];
child = parent;
parent = (child - 1) / 2;
}
array[child] = offered;
return true;
}
/*
1. 交换堆顶和尾部元素, 让尾部元素出队
2. (下潜)
- 从堆顶开始, 将父元素与两个孩子较大者交换
- 直到父元素大于两个孩子, 或没有孩子为止
*/
@Override
public E poll() {
if (isEmpty()) {
return null;
}
// 堆顶 与 堆底 交换，使被移除的元素成为数组末尾，方便移除。
// swap(0, --size);
swap(0, size - 1);
size--;
// 移除
Priority e = array[size];
array[size] = null; // help GC
// 新堆顶 下潜
down(0);
return (E) e;
}
private void down(int parent) {
// 左右孩子索引
int left = 2 * parent + 1;
int right = left + 1;
int max = parent; // 假设父元素优先级最高
// 两个孩子里找个大的 索引
if (left < size && array[left].priority() > array[max].priority()) {
max = left;
}
if (right < size && array[right].priority() > array[max].priority()) {
max = right;
}
// （此轮递归）发生了交换，说明有孩子比父亲大，交换，然后继续down(max)
if (max != parent) {
swap(max, parent);
down(max); // 递归
}
// 没有发生交换，直接结束返回
}
private void swap(int i, int j) {
Priority t = array[i];
array[i] = array[j];
array[j] = t;
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return (E) array[0];
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == array.length;
}
}
4.4 例题：合并多个有序链表
23. 合并 K 个升序链表（堆方法）
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
题目中要从小到大排列，因此选择用小顶堆来实现，自定义小顶堆如下
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6示例 2：
输入：lists = [] 输出：[]示例 3：
输入：lists = [[]] 输出：[]
MinHeap小顶堆 类：
/**
* <b>小顶堆</b>
*/
public class MinHeap {
/*
每次取链表的第一个元素进行比价，小的进入新链表，然后next
min
1->4->5->null
1->3->4->null
2->6->null
小顶堆
1 1 2 (选取第一个1，加入新链表，然后取下一个 2）
1 2 4
新链表
s->1
*/
ListNode[] array;
int size;
public MinHeap(int capacity) {
array = new ListNode[capacity];
}
public boolean offer(ListNode offered) {
if (isFull()) {
return false;
}
int child = size++;
int parent = (child - 1) / 2;
while (child > 0 && offered.val < array[parent].val) {
array[child] = array[parent];
child = parent;
parent = (child - 1) / 2;
}
array[child] = offered;
return true;
}
public ListNode poll() {
if (isEmpty()) {
return null;
}
swap(0, size - 1);
size--;
ListNode e = array[size];
array[size] = null; // help GC
// 下潜
down(0);
return e;
}
private void down(int parent) {
int left = 2 * parent + 1;
int right = left + 1;
int min = parent; // 假设父元素最小
if (left < size && array[left].val < array[min].val) {
min = left;
}
if (right < size && array[right].val < array[min].val) {
min = right;
}
if (min != parent) { // 有孩子比父亲小
swap(min, parent);
down(min);
}
}
private void swap(int i, int j) {
ListNode t = array[i];
array[i] = array[j];
array[j] = t;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == array.length;
}
}
方法：
public ListNode mergeKLists(ListNode[] lists) {
// 1. 使用 jdk 的优先级队列实现
// PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
MinHeap heap = new MinHeap(lists.length);
// 1. 将每个链表的头（第一个）节点加入小顶堆
for (ListNode h : lists) {
if(h != null) {
heap.offer(h);
}
}
// 2. 不断从堆顶移除最小元素, 加入新链表
ListNode s = new ListNode(-1, null);
ListNode t = s;
while(!heap.isEmpty()) {
ListNode min = heap.poll();
t.next = min;
t = min;
// 将最小元素的下一个节点加入到堆
if(min.next != null) {
heap.offer(min.next);
}
}
return s.next;
}
力扣官方题解：使用优先队列PriorityQueue合并
思路：
我们需要维护当前每个链表没有被合并的元素的最前面一个，
k个链表就最多有k个满足这样条件的元素，每次在这些元素里面选取val属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。
class Solution {
class Status implements Comparable<Status> {
int val;
ListNode ptr;
Status(int val, ListNode ptr) {
this.val = val;
this.ptr = ptr;
}
public int compareTo(Status status2) {
return this.val - status2.val;
}
}
PriorityQueue<Status> queue = new PriorityQueue<Status>();
public ListNode mergeKLists(ListNode[] lists) {
for (ListNode node: lists) {
if (node != null) {
queue.offer(new Status(node.val, node));
}
}
ListNode head = new ListNode(0);
ListNode tail = head;
while (!queue.isEmpty()) {
Status f = queue.poll();
tail.next = f.ptr;
tail = tail.next;
if (f.ptr.next != null) {
queue.offer(new Status(f.ptr.next.val, f.ptr.next));
}
}
return head.next;
}
}
5. 阻塞队列
5.1 问题引入
之前的队列在很多场景下都不能很好地工作，例如
- 大部分场景要求分离向队列放入（生产者）、从队列拿出（消费者）两个角色、它们得由不同的线程来担当，而之前的实现根本没有考虑线程安全问题
- 队列为空，那么在之前的实现里会返回 null，如果就是硬要拿到一个元素呢？只能不断循环尝试
- 队列为满，那么在之前的实现里会返回 false，如果就是硬要塞入一个元素呢？只能不断循环尝试
因此我们需要解决的问题有
- 用锁保证线程安全
- 用条件变量让等待非空线程与等待不满线程进入等待状态，而不是不断循环尝试，让 CPU 空转
举例，两个线程都要执行入队操作（几乎在同一时刻）
public class TestThreadUnsafe {
private final String[] array = new String[10];
private int tail = 0;
public void offer(String e) {
array[tail] = e;
tail++;
}
@Override
public String toString() {
return Arrays.toString(array);
}
public static void main(String[] args) {
TestThreadUnsafe queue = new TestThreadUnsafe();
new Thread(()-> queue.offer("e1"), "t1").start();
new Thread(()-> queue.offer("e2"), "t2").start();
}
}
执行的时间序列如下，假设初始状态 tail = 0，在执行过程中由于 CPU 在两个线程之间切换，造成了指令交错
| 线程1 | 线程2 | 说明 |
|---|---|---|
| array[tail]=e1 | 线程1 向 tail 位置加入 e1 这个元素，但还没来得及执行 tail++ | |
| array[tail]=e2 | 线程2 向 tail 位置加入 e2 这个元素，覆盖掉了 e1 | |
| tail++ | tail 自增为1 | |
| tail++ | tail 自增为2 | |
| 最后状态 tail 为 2，数组为 [e2, null, null ...] |
糟糕的是，由于指令交错的顺序不同，得到的结果不止以上一种，宏观上造成混乱的效果
5.2 单锁实现
Java 中要防止代码段交错执行，需要使用锁，有两种选择
synchronized代码块，属于关键字级别提供锁保护，功能少ReentrantLock类，功能丰富
以 ReentrantLock 为例
ReentrantLock lock = new ReentrantLock(); // 锁对象
public void offer(String e) {
// lock.lock(); // 加锁
lock.lockInterruptibly(); // 加锁(可以在阻塞状态随时打断)
try {
array[tail] = e;
tail++;
} finally {
lock.unlock(); // 解锁
}
}
只要两个线程执行上段代码时，锁对象是同一个，就能保证 try 块内的代码的执行不会出现指令交错现象，即执行顺序只可能是下面两种情况之一
| 线程1 | 线程2 | 说明 |
|---|---|---|
| lock.lockInterruptibly() | t1 对锁对象上锁 |
|
| array[tail]=e1 | ||
| lock.lockInterruptibly() | 即使 CPU 切换到线程2，但由于 t1 已经对该对象上锁，因此线程2卡在这儿进不去 |
|
| tail++ | 切换回线程1 执行后续代码 | |
| lock.unlock() | 线程1 解锁 | |
| array[tail]=e2 | 线程2 此时才能获得锁，执行它的代码 | |
| tail++ |
- 另一种情况是线程2 先获得锁，线程1 被挡在外面
- 要明白保护的本质，本例中是保护的是 tail 位置读写的安全
之前 isFull() 是返回 false 表示添加失败，前面分析过想达到这么一种效果：
- 在队列满时，不是立刻返回，而是当前线程进入等待
- 什么时候队列不满了，再唤醒这个等待的线程，从上次的代码处继续向下运行
ReentrantLock 可以配合条件变量来实现，代码进化为
ReentrantLock lock = new ReentrantLock(); // 锁对象
Condition tailWaits = lock.newCondition(); // 条件变量对象 集合
public void offer(String e) throws InterruptedException {
// lock.lock(); // 加锁
lock.lockInterruptibly(); // 加锁(可以在阻塞状态随时打断)
try {
while (isFull()) {
// 满了该做的事, offer 线程阻塞
tailWaits.await(); // 当前线程加入 tailWaits, 并且让此线程阻塞 tailWaits.signal()
}
array[tail] = e;
if(++tail == array.length) {
tail = 0;
}
size++;
} finally {
lock.unlock(); // 解锁
}
}
- 条件变量底层也是个队列，用来存储这些需要等待的线程，当队列满了，就会将
offer线程加入条件队列，并暂时释放锁 - 将来我们的队列如果不满了（由
poll线程那边得知）可以调用tailWaits.signal()来唤醒tailWaits中首个等待的线程，被唤醒的线程会再次抢到锁，从上次await处继续向下运行
思考为何要用 while 而不是 if，设队列容量是 3
| 操作前 | offer(4) | offer(5) | poll() | 操作后 |
|---|---|---|---|---|
| [1 2 3] | 队列满，进入tailWaits 等待 | [1 2 3] | ||
| [1 2 3] | 取走 1，队列不满，唤醒线程 | [2 3] | ||
| [2 3] | 抢先获得锁，发现不满，放入 5 | [2 3 5] | ||
| [2 3 5] | 从上次等待处直接向下执行 | [2 3 5 ?] |
关键点：
- 从 tailWaits 中唤醒的线程，会与新来的 offer 的线程争抢锁，谁能抢到是不一定的，如果后者先抢到，就会导致条件又发生变化
- 这种情况称之为虚假唤醒，唤醒后应该重新检查条件，看是不是得重新进入等待
最终实现代码：
BlockingQueue<E>接口：
public interface BlockingQueue<E> { // 阻塞队列
void offer(E e) throws InterruptedException;
boolean offer(E e, long timeout) throws InterruptedException;
E poll() throws InterruptedException;
}
实现类：
/**
* 单锁实现
* @param <E> 元素类型
*/
@SuppressWarnings("all")
public class BlockingQueue1<E> implements BlockingQueue<E> {
private final E[] array;
private int head;
private int tail;
private int size;
public BlockingQueue1(int capacity) {
array = (E[]) new Object[capacity];
}
private ReentrantLock lock = new ReentrantLock();
private Condition headWaits = lock.newCondition(); // poll
private Condition tailWaits = lock.newCondition(); // offer
private boolean isEmpty() {
return size == 0;
}
private boolean isFull() {
return size == array.length;
}
@Override
public void offer(E e) throws InterruptedException {
lock.lockInterruptibly();
try {
while (isFull()) {
tailWaits.await(); // 等多久
}
array[tail] = e;
if (++tail == array.length) {
tail = 0;
}
size++;
headWaits.signal();
} finally {
lock.unlock();
}
}
@Override
public boolean offer(E e, long timeout) throws InterruptedException { // 毫秒 5s
lock.lockInterruptibly();
try {
long t = TimeUnit.MILLISECONDS.toNanos(timeout); // 毫秒 转 纳秒
while (isFull()) {
if (t <= 0) {
return false;
}
t = tailWaits.awaitNanos(t); // 最多等待多少纳秒 1s 4s 返回值代表剩余时间
}
array[tail] = e;
if (++tail == array.length) {
tail = 0;
}
size++;
headWaits.signal();
return true;
} finally {
lock.unlock();
}
}
@Override
public E poll() throws InterruptedException {
lock.lockInterruptibly();
try {
while (isEmpty()) {
headWaits.await();
}
E e = array[head];
array[head] = null; // help GC
if (++head == array.length) {
head = 0;
}
size--;
tailWaits.signal();
return e;
} finally {
lock.unlock();
}
}
@Override
public String toString() {
return Arrays.toString(array);
}
}
public void offer(E e, long timeout) throws InterruptedException是带超时的版本，可以只等待一段时间，而不是永久等下去。
注意
JDK中BlockingQueue接口的方法命名与上面示例有些差异- 方法
offer(E e)是非阻塞的实现，阻塞实现方法为put(E e) - 方法
poll()是非阻塞的实现，阻塞实现方法为take()
- 方法
5.3 双锁实现
单锁的缺点在于：
- 生产和消费几乎是不冲突的，唯一冲突的是生产者和消费者它们有可能同时修改 size（
offer和poll不能同时进行） - 冲突的主要是生产者之间：多个
offer线程修改tail - 冲突的还有消费者之间：多个
poll线程修改head
如果希望进一步提高性能，可以用两把锁
- 一把锁保护
tail - 另一把锁保护
head
ReentrantLock headLock = new ReentrantLock(); // 保护 head 的锁
Condition headWaits = headLock.newCondition(); // 队列空时，需要等待的线程集合
ReentrantLock tailLock = new ReentrantLock(); // 保护 tail 的锁
Condition tailWaits = tailLock.newCondition(); // 队列满时，需要等待的线程集合
先看看 offer 方法的初步实现
@Override
public void offer(E e) throws InterruptedException {
tailLock.lockInterruptibly();
try {
// 队列满等待
while (isFull()) {
tailWaits.await();
}
// 不满则入队
array[tail] = e;
if (++tail == array.length) {
tail = 0;
}
// 修改 size （有问题）
size++;
} finally {
tailLock.unlock();
}
}
上面代码的缺点是 size 并不受 tailLock 保护，tailLock 与 headLock 是两把不同的锁，并不能实现互斥的效果。因此，size 需要用下面的代码保证原子性
AtomicInteger size = new AtomicInteger(0); // 保护 size 的原子变量
size.getAndIncrement(); // 自增
size.getAndDecrement(); // 自减
代码修改为
@Override
public void offer(E e) throws InterruptedException {
tailLock.lockInterruptibly();
try {
// 队列满等待
while (isFull()) {
tailWaits.await();
}
// 不满则入队
array[tail] = e;
if (++tail == array.length) {
tail = 0;
}
// 修改 size
size.getAndIncrement();
} finally {
tailLock.unlock();
}
}
对称地，可以写出 poll 方法
@Override
public E poll() throws InterruptedException {
E e;
headLock.lockInterruptibly();
try {
// 队列空等待
while (isEmpty()) {
headWaits.await();
}
// 不空则出队
e = array[head];
if (++head == array.length) {
head = 0;
}
// 修改 size
size.getAndDecrement();
} finally {
headLock.unlock();
}
return e;
}
下面来看一个难题，就是如何通知 headWaits 和 tailWaits 中等待的线程，比如 poll 方法拿走一个元素，通知 tailWaits：我拿走一个，不满了噢，你们可以放了，因此代码改为
@Override
public E poll() throws InterruptedException {
E e;
headLock.lockInterruptibly();
try {
// 队列空等待
while (isEmpty()) {
headWaits.await();
}
// 不空则出队
e = array[head];
if (++head == array.length) {
head = 0;
}
// 修改 size
size.getAndDecrement();
// 通知 tailWaits 不满（有问题）
tailWaits.signal();
} finally {
headLock.unlock();
}
return e;
}
问题在于要使用这些条件变量的 await()， signal() 等方法需要先获得与之关联的锁，上面的代码若直接运行会出现以下错误
java.lang.IllegalMonitorStateException
加上锁即可使用，但两把锁这么嵌套使用，非常容易出现死锁，如下所示
因此得避免嵌套，两段加锁的代码变成了下面平级的样子
性能还可以进一步提升
- 代码调整后
offer并没有同时获取tailLock和headLock两把锁，因此两次加锁之间会有空隙，这个空隙内可能有其它的 offer 线程添加了更多的元素，那么这些线程都要执行signal()，通知poll线程队列非空吗？- 每次调用
signal()都需要这些offer线程先获得headLock锁，成本较高，要想法减少offer线程获得headLock锁的次数 - 可以加一个条件：当
offer增加前队列为空，即从 0 变化到不空，才由此offer线程来通知headWaits，其它情况不归它管
- 每次调用
- 队列从 0 变化到不空，会唤醒一个等待的
poll线程，这个线程被唤醒后，肯定能拿到headLock锁，因此它具备了唤醒headWaits上其它poll线程的先决条件。如果检查出此时有其它offer线程新增了元素（不空，但不是从0变化而来），那么不妨由此poll线程来唤醒其它poll线程
这个技巧被称之为级联通知（cascading notifies），类似的原因
- 在 poll 时队列从满变化到不满，才由此
poll线程来唤醒一个等待的offer线程，目的也是为了减少poll线程对tailLock上锁次数，剩下等待的offer线程由这个offer线程间接唤醒
最终的代码为：
/**
* 双锁实现
* @param <E> 元素类型
*/
@SuppressWarnings("all")
public class BlockingQueue2<E> implements BlockingQueue<E> {
private final E[] array;
private int head;
private int tail;
// 原子整数类
private AtomicInteger size = new AtomicInteger();
private ReentrantLock tailLock = new ReentrantLock();
private Condition tailWaits = tailLock.newCondition();
private ReentrantLock headLock = new ReentrantLock();
private Condition headWaits = headLock.newCondition();
public BlockingQueue2(int capacity) {
this.array = (E[]) new Object[capacity];
}
private boolean isEmpty() {
return size.get() == 0;
}
private boolean isFull() {
return size.get() == array.length;
}
@Override
public String toString() {
return Arrays.toString(array);
}
@Override
public void offer(E e) throws InterruptedException {
int c; // 添加前元素个数
tailLock.lockInterruptibly();
try {
// 1. 队列满则等待
while (isFull()) {
tailWaits.await(); // offer2
}
// 2. 不满则入队
array[tail] = e;
if (++tail == array.length) {
tail = 0;
}
// 3. 修改 size
/*
size++;(存在问题） poll 和 offer同时操作会意外
1.读取size值
2.自增（poll 自减）
3.结果写回
size = 6
*/
c = size.getAndIncrement(); // 返回的是原来的值
// a. 队列不满, 但不是从满->不满, 由此offer线程唤醒其它offer线程
if (c + 1 < array.length) {
tailWaits.signal();
}
/*
1. 读取成员变量size的值 5
2. 自增 6
3. 结果写回成员变量size 6
*/
} finally {
tailLock.unlock();
}
// 4. 如果从0变为非空，由offer这边唤醒等待非空的poll线程
// 0->1 1->2 2->3
if(c == 0) {
headLock.lock(); // offer_1 offer_2 offer_3
try {
headWaits.signal();
} finally {
headLock.unlock();
}
}
}
@Override
public E poll() throws InterruptedException {
E e;
int c; // 取走前的元素个数
headLock.lockInterruptibly();
try {
// 1. 队列空则等待
while (isEmpty()) {
headWaits.await(); // poll_4
}
// 2. 非空则出队
e = array[head];
array[head] = null; // help GC
if (++head == array.length) {
head = 0;
}
// 3. 修改 size
c = size.getAndDecrement();
// 队列中还有元素，唤醒其他poll线程
// 3->2 2->1 1->0
// poll_1 poll_2 poll_3
// b. 队列不空, 但不是从0变化到不空，由此poll线程通知其它poll线程
if (c > 1) { // 减少前大于1
headWaits.signal();
}
/*
1. 读取成员变量size的值 5
2. 自减 4
3. 结果写回成员变量size 4
*/
} finally {
headLock.unlock();
}
// 4. 队列从满->不满时 由poll唤醒等待不满的 offer 线程
if(c == array.length) {
tailLock.lock();
try {
tailWaits.signal(); // ctrl+alt+t
} finally {
tailLock.unlock();
}
}
return e;
}
@Override
public boolean offer(E e, long timeout) throws InterruptedException {
return false;
}
public static void main(String[] args) throws InterruptedException {
BlockingQueue2<String> queue = new BlockingQueue2<>(3);
// queue.offer("元素1");
// queue.offer("元素2");
new Thread(()->{
try {
String poll = queue.poll();
System.out.println(poll);
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}, "poll").start();
new Thread(()->{
try {
String poll = queue.poll();
System.out.println(poll);
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}, "poll2").start();
new Thread(()->{
try {
queue.offer("元素3");
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}, "offer").start();
}
}
6. 堆
PriorityQueue，优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值最小的
6.1 Floyd建堆算法
Floyd 建堆算法作者（也是之前龟兔赛跑判环作者）：
- 找到最后一个非叶子节点
- 从后向前，对每个节点执行下潜
一些规律：
- 一棵满二叉树节点个数为
2^h-1，如下图中高度h=3节点数是2^3-1=7 - 非叶子节点范围为
[0, size/2-1]
算法时间复杂度分析
下面看交换次数的推导：设节点高度为 3
| 本层节点数 | 高度 | 下潜最多交换次数（高度-1） | |
|---|---|---|---|
| 4567 这层 | 4 | 1 | 0 |
| 23这层 | 2 | 2 | 1 |
| 1这层 | 1 | 3 | 2 |
每一层的交换次数为：节点个数*此节点交换次数，总的交换次数为
- 分子8为2的3次方（3为二叉树高度），分母2的n次方，n为所在高度。
即
在 https://www.wolframalpha.com/ 输入
Sum[\(40)Divide[Power[2,x],Power[2,i]]*\(40)i-1\(41)\(41),{i,1,x}]
推导出
其中 2^h \approx n，h \approx \log_2{n}，因此有时间复杂度 O(n)
6.2 完整代码
/**
* 大顶堆
*/
public class MaxHeap {
int[] array;
int size;
public MaxHeap(int capacity) {
this.array = new int[capacity];
}
public MaxHeap(int[] array) {
this.array = array;
this.size = array.length;
heapify();
}
// 建堆
private void heapify() {
// 找到最后这个非叶子节点，从后向前 size / 2 - 1
for (int i = size / 2 - 1; i >= 0; i--) {
down(i);
}
}
/**
* 获取堆顶元素
*
* @return 堆顶元素
*/
public int peek() {
// isEmpty return - 1
return array[0];
}
/**
* 删除堆顶元素
*
* @return 堆顶元素
*/
public int poll() {
// isEmpty return - 1
int top = array[0];
swap(0, size - 1); // 移除队尾，效率高
size--;
down(0);
return top;
}
/**
* 删除指定索引处元素
*
* @param index 索引
* @return 被删除元素
*/
public int poll(int index) {
int deleted = array[index];
swap(index, size - 1);
size--;
down(index);
return deleted;
}
/**
* 替换堆顶元素
*
* @param replaced 新元素
*/
public void replace(int replaced) {
array[0] = replaced;
down(0);
}
/**
* 堆的尾部添加元素
*
* @param offered 新元素
* @return 是否添加成功
*/
public boolean offer(int offered) {
if (size == array.length) {
return false;
}
up(offered);
size++;
return true;
}
// 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶
/**
* 用于插入元素
*
* @param offered 待添加的元素
*/
private void up(int offered) {
int child = size; // 将被插入点索引
while (child > 0) {
int parent = (child - 1) / 2;
if (offered > array[parent]) {
array[child] = array[parent];
} else {
break;
}
child = parent;
}
array[child] = offered;
}
// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大
private void down(int parent) {
int left = parent * 2 + 1;
int right = left + 1;
int max = parent;
// left >= size 说明没有孩子，直接end
if (left < size && array[left] > array[max]) {
max = left;
}
if (right < size && array[right] > array[max]) {
max = right;
}
if (max != parent) { // 找到了更大的孩子
swap(max, parent);
down(max);
}
// max = parent 说明不用继续下潜了
}
// 交换两个索引处的元素
private void swap(int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}
6.3 例题
6.3.1 堆排序
算法描述
heapify建立大顶堆- 将堆顶与堆底交换（最大元素被交换到堆底），堆缩小1，并下潜调整堆
- 重复第二步直至堆里剩一个元素
public static void main(String[] args) {
int[] array = {2, 3, 1, 7, 6, 4, 5};
MaxHeap heap = new MaxHeap(array);
// [7, 6, 5, 3, 2, 4, 1]
System.out.println(Arrays.toString(heap.array));
while (heap.size > 1) {
heap.swap(0, heap.size - 1);
heap.size--;
heap.down(0);
}
// [1, 2, 3, 4, 5, 6, 7]
System.out.println(Arrays.toString(heap.array));
}
6.3.2 数组中第K大元素
给定整数数组
nums和整数k，请返回数组中第k个最大的元素。请注意，你需要找的是数组排序后的第
k个最大的元素，而不是第k个不同的元素。你必须设计并实现时间复杂度为
O(n)的算法解决此问题。
输入: [3,2,1,5,6,4], k = 2
输出: 5
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
6.3.2.0 小顶堆
以小顶堆为例：
k为几，小顶堆就先加入几个元素，以上面第一条示例为例，依次加入 3,2，然后遍历原数组，1比堆顶2小，不加入；5比堆顶元素大，加入，调整后堆顶为3；...结束后，堆顶元素元素即为第 k 个最大的元素。
MinHeap小顶堆代码：
public class MinHeap {
int[] array;
int size;
public MinHeap(int capacity) {
this.array = new int[capacity];
}
public boolean isFull() {
return size == array.length;
}
/**
* 获取堆顶元素
*
* @return 堆顶元素
*/
public int peek() {
return array[0];
}
/**
* 删除堆顶元素
*
* @return 堆顶元素
*/
public int poll() {
int top = array[0];
swap(0, size - 1);
size--;
down(0);
return top;
}
/**
* 删除指定索引处元素
*
* @param index 索引
* @return 被删除元素
*/
public int poll(int index) {
int deleted = array[index];
swap(index, size - 1);
size--;
down(index);
return deleted;
}
/**
* 替换堆顶元素
*
* @param replaced 新元素
*/
public void replace(int replaced) {
array[0] = replaced;
down(0);
}
/**
* 堆的尾部添加元素
*
* @param offered 新元素
* @return 是否添加成功
*/
public boolean offer(int offered) {
if (size == array.length) {
return false;
}
up(offered);
size++;
return true;
}
// 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶
private void up(int offered) {
int child = size;
while (child > 0) {
int parent = (child - 1) / 2;
if (offered < array[parent]) {
array[child] = array[parent];
} else {
break;
}
child = parent;
}
array[child] = offered;
}
public MinHeap(int[] array) {
this.array = array;
this.size = array.length;
heapify();
}
// 建堆
private void heapify() {
// 如何找到最后这个非叶子节点 size / 2 - 1
for (int i = size / 2 - 1; i >= 0; i--) {
down(i);
}
}
// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大
private void down(int parent) {
int left = parent * 2 + 1;
int right = left + 1;
int min = parent;
if (left < size && array[left] < array[min]) {
min = left;
}
if (right < size && array[right] < array[min]) {
min = right;
}
if (min != parent) { // 找到了更大的孩子
swap(min, parent);
down(min);
}
}
// 交换两个索引处的元素
private void swap(int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}
方法代码：
/**
* <h3>求数组中第 K 大的元素</h3>
* <p>
* 解体思路
* <ol>
* <li>向小顶堆放入前k个元素</li>
* <li>剩余元素</li>
* <ul>
* <li>若 <= 堆顶元素, 则略过</li>
* <li>若 > 堆顶元素, 则替换堆顶元素</li>
* </ul>
* <li>这样小顶堆始终保留的是到目前为止, <b>前 K 大</b>的元素</li>
* <li>循环结束, 堆顶元素即为<b>第 K 大</b>元素</li>
* </ol>
*/
public class E02Leetcode215 {
public int findKthLargest(int[] numbers, int k) {
MinHeap heap = new MinHeap(k);
for (int i = 0; i < k; i++) {
heap.offer(numbers[i]);
}
for (int i = k; i < numbers.length; i++) {
if(numbers[i] > heap.peek()) {
heap.replace(numbers[i]);
}
}
return heap.peek();
}
public static void main(String[] args) {
// 应为5
System.out.println(new E02Leetcode215().findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2));
// 应为4
System.out.println(new E02Leetcode215().findKthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4));
}
}
求数组中的第 K 大元素，使用堆并不是最佳选择，可以采用快速选择算法
6.3.2.1 优先队列
力扣视频使用 PriorityQueue 实现：(思路类似)
力扣官方题解：
6.3.2.2 大根堆
思路和算法
我们也可以使用堆排序来解决这个问题——建立一个大根堆，做
k−1次删除操作后堆顶元素就是我们要找的答案。在很多语言中，都有优先队列或者堆的的容器可以直接使用，但是在面试中，面试官更倾向于让更面试者自己实现一个堆。所以建议读者掌握这里大根堆的实现方法，在这道题中尤其要搞懂「建堆」、「调整」和「删除」的过程。友情提醒：「堆排」在很多大公司的面试中都很常见，不了解的同学建议参考《算法导论》或者大家的数据结构教材，一定要学会这个知识点哦！^_^
class Solution {
public int findKthLargest(int[] nums, int k) {
int heapSize = nums.length;
buildMaxHeap(nums, heapSize);
for (int i = nums.length - 1; i >= nums.length - k + 1; --i) { // 从尾部减，方便删除
swap(nums, 0, i);
--heapSize;
maxHeapify(nums, 0, heapSize);
}
return nums[0];
}
public void buildMaxHeap(int[] a, int heapSize) {
for (int i = heapSize / 2; i >= 0; --i) {
maxHeapify(a, i, heapSize);
}
}
public void maxHeapify(int[] a, int i, int heapSize) {
int l = i * 2 + 1, r = i * 2 + 2, largest = i;
if (l < heapSize && a[l] > a[largest]) {
largest = l;
}
if (r < heapSize && a[r] > a[largest]) {
largest = r;
}
if (largest != i) {
swap(a, i, largest);
maxHeapify(a, largest, heapSize);
}
}
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
时间复杂度：
O(nlogn)，建堆的时间代价是O(n)，删除的总代价是O(klogn)，因为k<n，故渐进时间复杂为O(n+klogn)=O(nlogn)。
6.3.2.3 快速选择算法
public class Solution {
int[] nums;
/**
* 交换辅助函数
* @param a
* @param b
*/
public void swap(int a, int b) {
int tmp = this.nums[a];
this.nums[a] = this.nums[b];
this.nums[b] = tmp;
}
public int partition(int left, int right, int pivot_index) {
// 暂存轴值
int pivot = this.nums[pivot_index]; // 轴值元素
swap(pivot_index, right); // 为了方便比较，轴值放到最右边
int store_index = left; // 初始第一个比轴值小的位置，即最左边
// 遍历数组调整轴值位置
for (int i = left; i <= right; i++) {
if (this.nums[i] < pivot) {
// 小于轴值的元素，放到左侧（store index处），后++
swap(store_index, i);
store_index++;
}
}
// 遍历完后，把轴值放到预期位置
swap(store_index, right);
return store_index;
}
/**
* 选取一个轴值，根据调整后轴值的位置和k的相对关系，进行进一步递归搜索
* @param left
* @param right
* @param k_smallest
* @return
*/
public int quickselect(int left, int right, int k_smallest) {
// 定义递归出口
if (left == right) {
return this.nums[left];
}
// 随机生成轴值（索引）
Random random_num = new Random();
int pivot_index = left + random_num.nextInt(right - left);
// 获取正确的轴值位置
pivot_index = partition(left, right, pivot_index);
// 根据轴值位置，递归搜索对应半边
if (k_smallest == pivot_index) {
return this.nums[k_smallest];
} else if ((k_smallest < pivot_index)) {
return quickselect(left, pivot_index - 1, k_smallest);
} else {
return quickselect(pivot_index + 1, right, k_smallest);
}
}
public int findKthLargest(int[] nums, int k) {
this.nums = nums;
int size = nums.length;
return quickselect(0, size - 1, size - k); // 第k大 → 从小到大 第 size - k
}
}
时间复杂度：
O(n)
上诉代码扔进力扣已经超时，更新官方代码：
class Solution {
int quickselect(int[] nums, int l, int r, int k) {
if (l == r) return nums[k];
int x = nums[l], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (nums[i] < x);
do j--; while (nums[j] > x);
if (i < j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
if (k <= j) return quickselect(nums, l, j, k);
else return quickselect(nums, j + 1, r, k);
}
public int findKthLargest(int[] _nums, int k) {
int n = _nums.length;
return quickselect(_nums, 0, n - 1, n - k);
}
}
6.3.3 数据流中的第 K 大元素
- 设计一个找到数据流中第
k大元素的类（class）。注意是排序后的第k大元素，不是第k个不同的元素。请实现KthLargest类：
KthLargest(int k, int[] nums)使用整数k和整数流nums初始化对象。int add(int val)将val插入数据流nums后，返回当前数据流中第k大的元素。- 题目数据保证，在查找第
k大元素时，数组中至少有k个元素
使用上题的小顶堆可解，创建容量为
k的小顶堆，添加数据时，没满则继续添加，满了则返回堆顶。示例：
输入： ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] 输出： [null, 4, 5, 5, 8, 8] 解释： KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8
代码：
class KthLargest {
private MinHeap heap;
public KthLargest(int k, int[] nums) {
heap = new MinHeap(k);
for(int i = 0; i < nums.length; i++) {
add(nums[i]);
}
}
public int add(int val) {
if(!heap.isFull()){
heap.offer(val);
} else if(val > heap.peek()){
heap.replace(val);
}
return heap.peek();
}
}
求数据流中的第 K 大元素，使用堆最合适不过
力扣官方解答：
我们可以使用一个大小为 k 的优先队列（小顶堆，poll是最小的）来存储前 k 大的元素，其中优先队列的队头为队列中最小的元素，也就是第 k 大的元素。
在单次插入的操作中，我们首先将元素
val加入到优先队列中。如果此时优先队列的大小大于 k，我们需要将优先队列的队头元素弹出，以保证优先队列的大小为 k。
class KthLargest {
PriorityQueue<Integer> pq;
int k;
public KthLargest(int k, int[] nums) {
this.k = k;
pq = new PriorityQueue<Integer>();
for (int x : nums) {
add(x); // 这里是add, 不是 pq的offer()
}
}
public int add(int val) {
pq.offer(val);
if (pq.size() > k) {
pq.poll();
}
return pq.peek();
}
}
6.3.4 数据流的中位数
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]的中位数是3。- 例如
arr = [2,3]的中位数是(2 + 3) / 2 = 2.5。实现
MedianFinder类:
MedianFinder()初始化MedianFinder对象。void addNum(int num)将数据流中的整数num添加到数据结构中。double findMedian()返回到目前为止所有元素的中位数。与实际答案相差10^{-5}以内的答案将被接受。
示例 1：
输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0] 解释 MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0
使用大顶堆+小顶堆：
为了保证两边数据量的平衡
- 两边个数一样时，左边个数加一
- 两边个数不一样时，右边个数加一
但是, 随便一个数能直接加入吗？
- 左边（大顶堆）个数加一时，把新元素加在右边（小顶堆），弹出（poll）右边最小的加入左边。（使得右边最小的，加入左边后，成为左边最大的）
- 右边（小顶堆）个数加一时，把新元素加在左边（大顶堆），弹出左边最小的加入右边
方法1：使用PriorityQueue
/**
* <h3>数据流的中位数</h3>
*/
public class E04Leetcode295_2 {
// 大顶堆
private PriorityQueue<Integer> left = new PriorityQueue<>(
(a, b) -> Integer.compare(b, a) //
);
// 小顶堆（默认）
private PriorityQueue<Integer> right = new PriorityQueue<>(
(a, b) -> Integer.compare(a, b) //
);
/**
* 为了保证两边数据量的平衡
* <ul>
* <li>两边个数一样时,左边个数加一</li>
* <li>两边个数不一样时,右边个数加一</li>
* </ul>
* 但是, 随便一个数能直接加入吗?
* <ul>
* <li>左边个数加一时, 把新元素加在右边，弹出右边最小的加入左边</li>
* <li>右边个数加一时, 把新元素加在左边，弹出左边最小的加入右边</li>
* </ul>
*/
public void addNum(int num) {
if (left.size() == right.size()) {
right.offer(num);
left.offer(right.poll());
} else {
left.offer(num);
right.offer(left.poll());
}
}
/**
* <ul>
* <li>两边数据一致, 左右各取堆顶元素求平均</li>
* <li>左边多一个, 取左边堆顶元素</li>
* </ul>
*/
public double findMedian() {
if (left.size() == right.size()) {
return (left.peek() + right.peek()) / 2.0;
} else {
return left.peek();
}
}
public static void main(String[] args) {
// 以上浮为例, 大概的实现逻辑
// Comparator<Integer> cmp = (a, b) -> Integer.compare(a, b); // 小顶堆比较器 compare -1 a<b, 0 a==b, 1 a>b
Comparator<Integer> cmp = (a, b) -> Integer.compare(b, a); // 大顶堆比较器 compare -1 b<a, 0 b==a, 1 b>a
int a = 10; // 父元素值
int b = 20; // 新增元素值
if (cmp.compare(a, b) > 0) {
System.out.println("上浮");
} else {
System.out.println("停止上浮");
}
}
}
方法2：创建Heap类，根据参数决定大顶堆或是小顶堆逻辑
Heap类：
/**
* 可以扩容的 heap, max 用于指定是大顶堆还是小顶堆
*/
public class Heap {
int[] array;
int size;
boolean max;
public int size() {
return size;
}
public Heap(int capacity, boolean max) {
this.array = new int[capacity];
this.max = max;
}
/**
* 获取堆顶元素
*
* @return 堆顶元素
*/
public int peek() {
return array[0];
}
/**
* 删除堆顶元素
*
* @return 堆顶元素
*/
public int poll() {
int top = array[0];
swap(0, size - 1);
size--;
down(0);
return top;
}
/**
* 删除指定索引处元素
*
* @param index 索引
* @return 被删除元素
*/
public int poll(int index) {
int deleted = array[index];
swap(index, size - 1);
size--;
down(index);
return deleted;
}
/**
* 替换堆顶元素
*
* @param replaced 新元素
*/
public void replace(int replaced) {
array[0] = replaced;
down(0);
}
/**
* 堆的尾部添加元素
*
* @param offered 新元素
*/
public void offer(int offered) {
if (size == array.length) {
// 扩容
grow();
}
up(offered);
size++;
}
private void grow() {
int newCapacity = size + (size >> 1);
int[] newArray = new int[newCapacity];
System.arraycopy(array, 0,
newArray, 0, size);
array = newArray;
}
// 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶
private void up(int offered) {
int child = size;
while (child > 0) {
int parent = (child - 1) / 2;
boolean cmp = max ? offered > array[parent] : offered < array[parent];
if (cmp) {
array[child] = array[parent];
} else {
break;
}
child = parent;
}
array[child] = offered;
}
public Heap(int[] array, boolean max) {
this.array = array;
this.size = array.length;
this.max = max;
heapify();
}
// 建堆
private void heapify() {
// 如何找到最后这个非叶子节点 size / 2 - 1
for (int i = size / 2 - 1; i >= 0; i--) {
down(i);
}
}
// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大
private void down(int parent) {
int left = parent * 2 + 1;
int right = left + 1;
int maxOrMin = parent;
if (left < size && (max ? array[left] > array[maxOrMin] : array[left] < array[maxOrMin])) {
maxOrMin = left;
}
if (right < size && (max ? array[right] > array[maxOrMin] : array[right] < array[maxOrMin])) {
maxOrMin = right;
}
if (maxOrMin != parent) { // 找到了更大的孩子
swap(maxOrMin, parent);
down(maxOrMin);
}
}
// 交换两个索引处的元素
private void swap(int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
public static void main(String[] args) {
// 扩容测试
Heap left = new Heap(5, true);
for (int i = 1; i <= 10; i++) {
left.offer(i);
System.out.println(Arrays.toString(left.array));
}
}
}
实现类：
/**
* <h3>数据流的中位数</h3>
*/
public class E04Leetcode295_1 {
public void addNum(int num) {
if (left.size() == right.size()) {
right.offer(num);
left.offer(right.poll());
} else {
left.offer(num);
right.offer(left.poll());
}
}
private Heap left = new Heap(10, true);
private Heap right = new Heap(10, false);
@Override
public String toString() {
int size = left.size;
int[] left = new int[size]; // left显示结果为倒序
for (int i = 0; i < left.length; i++) {
left[size - 1 - i] = this.left.array[i];
}
int[] right = Arrays.copyOf(this.right.array, this.right.size);
return Arrays.toString(left) + " <-> " + Arrays.toString(right);
}
/**
* <ul>
* <li>两边数据一致, 左右各取堆顶元素求平均</li>
* <li>左边多一个, 取左边堆顶元素</li>
* </ul>
*/
public double findMedian() {
if (left.size() == right.size()) {
return (left.peek() + right.peek()) / 2.0;
} else {
return left.peek();
}
}
public static void main(String[] args) {
E04Leetcode295_1 test = new E04Leetcode295_1();
test.addNum(1);
test.addNum(2);
test.addNum(3);
test.addNum(7);
test.addNum(8);
test.addNum(9);
System.out.println(test);
System.out.println(test.findMedian());
test.addNum(10);
System.out.println(test);
System.out.println(test.findMedian());
test.addNum(4);
System.out.println(test);
System.out.println(test.findMedian());
}
}
7. 二叉树
二叉树是这么一种树状结构：每个节点最多有两个孩子，左孩子和右孩子
TreeNode类：
/**
* <h3>树节点类</h3>
*/
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
public TreeNode(TreeNode left, int val, TreeNode right) {
this.left = left;
this.val = val;
this.right = right;
}
@Override
public String toString() {
return String.valueOf(this.val);
}
}
7.1 重要的二叉树结构
- 完全二叉树（complete binary tree）是一种二叉树结构，除最后一层以外，每一层都必须填满，填充时要遵从先左后右
- 平衡二叉树（balance binary tree）是一种二叉树结构，其中每个节点的左右子树高度相差不超过 1
7.2 存储
存储方式分为两种
- 定义树节点与左、右孩子引用（TreeNode）
- 使用数组，前面讲堆时用过，若以 0 作为树的根，索引可以通过如下方式计算
- 父 = floor((子 - 1) / 2)
- 左孩子 = 父 * 2 + 1
- 右孩子 = 父 * 2 + 2
7.3 遍历
遍历也分为两种
- 广度优先遍历（Breadth-first order）：尽可能先访问距离根最近的节点，也称为层序遍历
- 深度优先遍历（Depth-first order）：对于二叉树，可以进一步分成三种（要深入到叶子节点）核心在于什么时候访问 父节点
- pre-order 前序遍历，对于每一棵子树，先访问该节点，然后是左子树，最后是右子树
- in-order 中序遍历，对于每一棵子树，先访问左子树，然后是该节点，最后是右子树
- post-order 后序遍历，对于每一棵子树，先访问左子树，然后是右子树，最后是该节点
7.3.1 广度优先
| 本轮开始时队列 | 本轮访问节点 |
|---|---|
| [1] | 1 |
| [2, 3] | 2 |
| [3, 4] | 3 |
| [4, 5, 6] | 4 |
| [5, 6] | 5 |
| [6, 7, 8] | 6 |
| [7, 8] | 7 |
| [8] | 8 |
| [] |
- 初始化，将根节点加入队列
- 循环处理队列中每个节点，直至队列为空
- 每次循环内处理节点后，将它的孩子节点（即下一层的节点）加入队列
注意：
- 以上用队列来层序遍历是针对
TreeNode这种方式表示的二叉树- 对于数组表现的二叉树，则直接遍历数组即可，自然为层序遍历的顺序
7.3.2 深度优先
相关力扣例题：
前序：1 2 4 3 5 6
中序：4 2 1 5 3 6
后序：4 2 5 6 3 1
| 栈暂存 | 已处理 | 前序遍历 | 中序遍历 |
|---|---|---|---|
| [1] | 1 ✔️ 左💤 右💤 | 1 | |
| [1, 2] | 2✔️ 左💤 右💤 1✔️ 左💤 右💤 |
2 | |
| [1, 2, 4] | 4✔️ 左✔️ 右✔️ 2✔️ 左💤 右💤 1✔️ 左💤 右💤 |
4 | 4 |
| [1, 2] | 2✔️ 左✔️ 右✔️ 1✔️ 左💤 右💤 |
2 | |
| [1] | 1✔️ 左✔️ 右💤 | 1 | |
| [1, 3] | 3✔️ 左💤 右💤 1✔️ 左✔️ 右💤 |
3 | |
| [1, 3, 5] | 5✔️ 左✔️ 右✔️ 3✔️ 左💤 右💤 1✔️ 左✔️ 右💤 |
5 | 5 |
| [1, 3] | 3✔️ 左✔️ 右💤 1✔️ 左✔️ 右💤 |
3 | |
| [1, 3, 6] | 6✔️ 左✔️ 右✔️ 3✔️ 左✔️ 右💤 1✔️ 左✔️ 右💤 |
6 | 6 |
| [1, 3] | 3✔️ 左✔️ 右✔️ 1✔️ 左✔️ 右💤 |
||
| [1] | 1✔️ 左✔️ 右✔️ | ||
| [] |
7.3.2.1 递归实现
public class TreeTraversal {
public static void main(String[] args) {
/*
1
/ \
2 3
/ / \
4 5 6
*/
TreeNode root = new TreeNode(
new TreeNode(new TreeNode(4), 2, null),
1,
new TreeNode(new TreeNode(5), 3, new TreeNode(6))
);
preOrder(root); // 1 2 4 3 5 6
System.out.println();
inOrder(root); // 4 2 1 5 3 6
System.out.println();
postOrder(root); // 4 2 5 6 3 1
System.out.println();
}
/**
* <h3>前序遍历</h3>
* @param node 节点
*/
static void preOrder(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.val + "\t"); // 打印当前节点值
preOrder(node.left); // 左子树 一样遵守 前序规则 进行遍历
preOrder(node.right); // 右
}
/**
* <h3>中序遍历</h3>
* @param node 节点
*/
static void inOrder(TreeNode node) {
if (node == null) {
return;
}
inOrder(node.left); // 左
System.out.print(node.val + "\t"); // 值
inOrder(node.right); // 右
}
/**
* <h3>后序遍历</h3>
* @param node 节点
*/
static void postOrder(TreeNode node) {
if (node == null) {
return;
}
postOrder(node.left); // 左
postOrder(node.right); // 右
System.out.print(node.val + "\t"); // 值
}
}
7.3.2.2 非递归实现
使用栈记录
测试用例及结果：
彩色打印代码：
// 需要时导入
import static algorithms.binarytree.E01Leetcode144.colorPrintln;
/*
31 红
32 黄
33 橙
34 蓝
35 紫
36 绿
*/
public static void colorPrintln(String origin, int color) {
System.out.printf("\033[%dm%s\033[0m%n", color, origin);
}
基础版本代码：
前序遍历，及中序遍历：
public static void main(String[] args) {
TreeNode root = new TreeNode(
new TreeNode(new TreeNode(4), 2, null),
1,
new TreeNode(new TreeNode(5), 3, new TreeNode(6))
);
// LinkedList<TreeNode> stack = new LinkedList<>();
LinkedListStack<TreeNode> stack = new LinkedListStack<>();
TreeNode curr = root; // 代表当前节点
while (curr != null || !stack.isEmpty()) { // 或者
if(curr != null) { // 往左边走到头
// =======================================
// 输出结果是 前序遍历
// =======================================
colorPrintln("去: " + curr.val,31);
stack.push(curr); // 压入栈，为了记住回来的路
curr = curr.left;
} else { // 左边走到头了，该回了
TreeNode pop = stack.pop();
// =======================================
// 弹出后打印， 输出结果是 中序遍历
// =======================================
colorPrintln("回: " + pop.val,34);
curr = pop.right; // 弹栈，判断父节点的右子节点
}
}
}
区别：前序遍历要先打印当前节点，再处理其左右节点。中序弹栈的说明其左节点已处理完，再打印。
力扣迭代代码：
/**
* 前序遍历：思路一样，不过这里使用 while 疯狂走到底
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
res.add(node.val);
stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;
}
return res;
}
}
后续遍历：
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curr = root; // 代表当前节点
TreeNode pop = null; // 最近一次弹栈的元素
while (!stack.isEmpty() || curr != null) {
// 往左走到底
if (curr != null) {
// colorPrintln("去：" + curr.val, 31);
stack.push(curr);
curr = curr.left;
// 走到底了
} else {
TreeNode peek = stack.peek();
// 没有右子树（右边自动处理完成），或者右节点已经弹栈（右边处理完成了）
if (peek.right == null || peek.right == pop) {
pop = stack.pop();
colorPrintln("回：" + pop.val, 34);
// 右边没有处理完成，先处理右边
} else {
curr = peek.right;
}
}
}
对于后序遍历，向回走时，需要处理完右子树才能 pop 出栈。如何知道右子树处理完成呢？
- 如果栈顶元素的
right \equiv null表示没啥可处理的，可以出栈 - 如果栈顶元素的
right \neq null，- 那么使用 lastPop 记录最近出栈的节点，即表示从这个节点向回走
- 如果栈顶元素的
right==lastPop此时应当出栈
对于前、中两种遍历，实际以上代码从右子树向回走时，并未走完全程（stack 提前出栈了）后序遍历以上代码是走完全程了
All in One 统一写法：
下面是一种统一的写法，依据后序遍历修改
public static void main(String[] args) {
TreeNode root = new TreeNode(
new TreeNode(new TreeNode(4), 2, new TreeNode(5)),
1,
new TreeNode(new TreeNode(6), 3, new TreeNode(7))
);
// System.out.println(new E03Leetcode145().postorderTraversal(root));
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curr = root; // 代表当前节点
TreeNode pop = null; // 最近一次弹栈的元素
while (!stack.isEmpty() || curr != null) {
if (curr != null) {
stack.push(curr);
// 前序遍历，在处理左子树前打印
colorPrintln("前:" + curr.val, 31);
// 待处理左子树
curr = curr.left;
} else {
TreeNode peek = stack.peek();
// 没有右子树
if (peek.right == null) {
// 按中序遍历，该打印该节点，再处理右子树，而右子树为null，则说明处理完毕，回弹到上级。
colorPrintln("中:" + peek.val, 36);
pop = stack.pop();
// 没有右子树，也算完成了右子树，按后序遍历，也该打印该节点
// colorPrintln("后:" + pop.val, 34);
}
// 右子树处理完成
// 最近一次弹栈的元素，刚好是peek的右节点，说明可以弹栈
else if (peek.right == pop) {
pop = stack.pop();
// 后序办理在 右子树处理完成后打印
// colorPrintln("后:" + pop.val, 34);
}
// 待处理右子树
else {
// 处理完左子树，处理右子树前打印
colorPrintln("中:" + peek.val, 36);
curr = peek.right;
}
}
}
}
7.3.2.3 Morris解法
Morris 遍历使用二叉树节点中大量指向 null 的指针，由 Joseph Morris 于 1979 年发明。
时间复杂度：O(n)
额外空间复杂度：O(1)
Morris 的整体思路就是将 以某个根结点开始，找到它左子树的最右侧节点之后与这个根结点进行连接
我们可以从 上图图2 看到，如果这么连接之后，cur 这个指针是可以完整的从一个节点顺着下一个节点遍历，将整棵树遍历完毕，直到 7 这个节点右侧没有指向。
public static void preOrderMorris(TreeNode head) {
if (head == null) {
return;
}
TreeNode cur1 = head;//当前开始遍历的节点
TreeNode cur2 = null;//记录当前结点的左子树
while (cur1 != null) {
cur2 = cur1.left;
if (cur2 != null) {
while (cur2.right != null && cur2.right != cur1) {//找到当前左子树的最右侧节点，且这个节点应该在指向根结点之前，否则整个节点又回到了根结点。
cur2 = cur2.right;
}
if (cur2.right == null) {//这个时候如果最右侧这个节点的右指针没有指向根结点，创建连接然后往下一个左子树的根结点进行连接操作。
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {//当左子树的最右侧节点有指向根结点，此时说明我们已经回到了根结点并重复了之前的操作，同时在回到根结点的时候我们应该已经处理完 左子树的最右侧节点 了，把路断开。
cur2.right = null;
}
}
cur1 = cur1.right;//一直往右边走，参考图
}
}
前序遍历
- 在某个根结点创建连线的时候打印。因为我们是顺着左边的根节点来创建连线，且创建的过程只有一次。
- 打印某些自身无法创建连线的节点，也就是叶子节点。
public static void preOrderMorris(TreeNode head) {
if (head == null) {
return;
}
TreeNode cur1 = head;
TreeNode cur2 = null;
while (cur1 != null) {
cur2 = cur1.left;
if (cur2 != null) {
while (cur2.right != null && cur2.right != cur1) {
cur2 = cur2.right;
}
if (cur2.right == null) {
cur2.right = cur1;
System.out.print(cur1.value + " "); // =======
cur1 = cur1.left;
continue;
} else {
cur2.right = null;
}
} else {
System.out.print(cur1.value + " "); // =======
}
cur1 = cur1.right;
}
}
中序遍历
从最左侧开始顺着右节点打印。也就是在将 cu1 切换到上层节点的时候。
public static void inOrderMorris(TreeNode head) {
if (head == null) {
return;
}
TreeNode cur1 = head;
TreeNode cur2 = null;
while (cur1 != null) {
cur2 = cur1.left;
//构建连接线
if (cur2 != null) {
while (cur2.right != null && cur2.right != cur1) {
cur2 = cur2.right;
}
if (cur2.right == null) {
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {
cur2.right = null;
}
}
System.out.print(cur1.value + " "); // =======
cur1 = cur1.right;
}
}
后序遍历
后序遍历就比较复杂了哈，先看一下图
当我们到达最左侧，也就是左边连线已经创建完毕了。
打印 4
打印 5 2
打印 6
打印 7 3 1
我们将一个节点的连续右节点当成一个单链表来看待。
当我们返回上层之后，也就是将连线断开的时候，打印下层的单链表。
比如返回到 ２，此时打印 ４
比如返回到 １，此时打印 ５ ２
比如返回到 ３，此时打印 ６
那么我们只需要将这个单链表逆序打印就行了，下文也给出了 单链表逆序代码
这里不应该打印当前层，而是下一层，否则根结点会先与右边打印。
//后序Morris
public static void postOrderMorris(TreeNode head) {
if (head == null) {
return;
}
TreeNode cur1 = head;//遍历树的指针变量
TreeNode cur2 = null;//当前子树的最右节点
while (cur1 != null) {
cur2 = cur1.left;
if (cur2 != null) {
while (cur2.right != null && cur2.right != cur1) {
cur2 = cur2.right;
}
if (cur2.right == null) {
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {
cur2.right = null;
postMorrisPrint(cur1.left);
}
}
cur1 = cur1.right;
}
postMorrisPrint(head); // 按上图是 1 → 3 → 7 反转后就是 7 → 3 → 1
}
//打印函数
public static void postMorrisPrint(TreeNode head) {
TreeNode reverseList = postMorrisReverseList(head);
TreeNode cur = reverseList;
while (cur != null) {
System.out.print(cur.value + " ");
cur = cur.right;
}
postMorrisReverseList(reverseList);
}
//翻转单链表
public static TreeNode postMorrisReverseList(TreeNode head) {
TreeNode cur = head;
TreeNode pre = null;
while (cur != null) {
TreeNode next = cur.right;
cur.right = pre;
pre = cur;
cur = next;
}
return pre;
}
7.4 例题
7.4.1 对称二叉树
给你一个二叉树的根节点
root， 检查它是否轴对称。
输入：root = [1,2,2,3,4,4,3]
输出：true
方法一，递归：
root节点不需要判断，需要判断root的左等不等于右。左的左 等不等于右的右；左的右等不等于右的左。
public boolean isSymmetric(TreeNode root) {
return check(root.left, root.right);
}
// left root左半边 right root右半边
public boolean check(TreeNode left, TreeNode right) {
// 若同时为 null
if (left == null && right == null) {
return true;
}
// 若有一个为 null (有上一轮筛选，另一个肯定不为 null)
if (left == null || right == null) {
return false;
}
/**
* 这里如果比较值相等 而 返回ture 下面的递归则走不到
*/
if (left.val != right.val) {
return false;
}
// 你往左 我往右 形成对称
return check(left.left, right.right) && check(left.right, right.left);
}
方法二，迭代（队列）：
思路同方法1，初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
public boolean check(TreeNode u, TreeNode v) {
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(u);
q.offer(v);
while (!q.isEmpty()) {
u = q.poll();
v = q.poll();
if (u == null && v == null) {
continue; // 不入队
}
if ((u == null || v == null) || (u.val != v.val)) {
return false;
}
q.offer(u.left);
q.offer(v.right);
q.offer(u.right);
q.offer(v.left);
}
return true;
}
}
类似题目：
7.4.2 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
方法一：递归，深度优先
如果我们知道了左子树和右子树的最大深度
l和r，那么该二叉树的最大深度即为max(l,r) + 1，而左子树和右子树的最大深度又可以以同样的方式进行计算。
/*
思路：
1. 得到左子树深度, 得到右子树深度, 二者最大者加一, 就是本节点深度
2. 因为需要先得到左右子树深度, 很显然是后序遍历典型应用
3. 关于深度的定义：从根出发, 离根最远的节点总边数,
注意: 力扣里的深度定义要多一 (chatGPT同)
深度2 深度3 深度1
1 1 1
/ \ / \
2 3 2 3
\
4
*/
public int maxDepth(TreeNode node) {
if (node == null) {
return 0; // 非力扣题目改为返回 -1
}
int d1 = maxDepth(node.left);
int d2 = maxDepth(node.right);
return Integer.max(d1, d2) + 1;
}
方法二：非递归，后序遍历
使用后序遍历，
stack的最大高度即为最大深度。stack.size()
/*
思路：
1. 使用非递归后序遍历, 栈的最大高度即为最大深度
*/
public int maxDepth(TreeNode root) {
TreeNode curr = root;
TreeNode pop = null;
LinkedList<TreeNode> stack = new LinkedList<>();
int max = 0; // 栈的最大高度
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
stack.push(curr);
// 更新 栈 更新 最大值
int size = stack.size();
if (size > max) {
max = size;
}
curr = curr.left;
} else {
TreeNode peek = stack.peek();
if (peek.right == null || peek.right == pop) {
pop = stack.pop();
} else {
curr = peek.right;
}
}
}
return max;
}
方法三：层序遍历求解（广度优先搜索）
此时我们广度优先搜索的队列里存放的是「当前层的所有节点」。每次拓展下一层的时候，不同于广度优先搜索的每次只从队列里拿出一个节点，我们需要将队列里的所有节点都拿出来进行拓展，这样能保证每次拓展完的时候队列里存放的是当前层的所有节点，即我们是一层一层地进行拓展，最后我们用一个变量
level来维护拓展的次数，该二叉树的最大深度即为level。
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size(); // 当前层 有多少node
// 用for也可以
// for (int i = 0; i < size; i++) {}
while (size > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
level++;
}
return level;
}
}
7.4.3 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
输入：root = [3,9,20,null,null,15,7]
输出：2
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
方法一：深度优先
如果是斜着向下的，其实就不用考虑左边了，递归右边就行。
初始个人代码：
public int minDepth(TreeNode root) {
if(root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
if (root.left == null) {
return minDepth(root.right) + 1;
}
if (root.right == null) {
return minDepth(root.left) + 1;
}
int leftMin = minDepth(root.left);
int rightMin = minDepth(root.right);
return Integer.min(leftMin, rightMin) + 1;
}
代码优化点：如果
node.left或node.right==null，那么递归调用会返回0，此时可以合并到一个if中。
public int minDepth(TreeNode node) {
if (node == null) {
return 0;
}
int d1 = minDepth(node.left);
int d2 = minDepth(node.right);
// 代码合并
if (d1 == 0 || d2 == 0) { // 因为d1 或 d2 = 0,所以相加没问题
return d1 + d2 + 1;
}
return Integer.min(d1, d2) + 1;
}
相较于求最大深度，应当考虑：
- 当右子树为
null，应当返回左子树深度加一 - 当左子树为
null，应当返回右子树深度加一
上面两种情况满足时，不应该再把为 null 子树的深度 0 参与最小值比较，例如这样：
1
/
2
- 正确深度为 2，若把为 null 的右子树的深度 0 考虑进来，会得到错误结果 1
1
\
3
\
4
- 正确深度为 3，若把为 null 的左子树的深度 0 考虑进来，会得到错误结果 1
方法二：层序遍历求解，广度优先（效率高）
遇到的第一个叶子节点所在层就是最小深度
例如，下面的树遇到的第一个叶子节点 3 所在的层就是最小深度，其他 4，7 等叶子节点深度更深，也更晚遇到
1
/ \
2 3
/ \
4 5
/
7
代码：
public static int minDepth2(TreeNode root) {
if (root == null) {
return 0;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
int level = 1; // root 为 第一层， return代码在for循环中，不会触及底部level++, 需要提前+1层 或者【把 level++ 移到 int size 下面】
while (!deque.isEmpty()) {
int size = deque.size();
for (int i = 0; i < size; i++) {
TreeNode cur = deque.poll();
// 最先触碰到叶子节点，说明可以返回了
if (cur.right == null && cur.left == null){
return level;
}
if (cur.left!=null){
deque.offer(cur.left);
}
if (cur.right!=null){
deque.offer(cur.right);
}
}
level++;
}
return level; // 基本走不到这行
}
7.4.4 翻转二叉树
给你一棵二叉树的根节点
root，翻转这棵二叉树，并返回其根节点。
示例：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点
root的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以root为根节点的整棵子树的翻转。
public TreeNode invertTree(TreeNode root) {
// 递归函数的终止条件，节点为空时返回
if (root == null) {
return null;
}
// 下面三句是将当前节点的左右子树交换
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
//递归交换当前节点的 左子树
invertTree(root.left);
//递归交换当前节点的 右子树
invertTree(root.right);
//函数返回时就表示当前这个节点，以及它的左右子树
//都已经交换完了
return root;
}
// ==================================================================
// 力扣简化写法：
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
先交换、再递归或是先递归、再交换都可以
7.4.5 后缀表达式转二叉树
中缀表达式 (2-1)*3
后缀（逆波兰）表达式 21-3*
1.遇到数字入栈
2.遇到运算符, 出栈两次, 与当前节点建立父子关系, 当前节点入栈
栈
| |
| |
| |
_____
表达式树
*
/ \
- 3
/ \
2 1
21-3*
思路：遇到数字，做成节点压入栈。
遇到字符，做成节点。然后栈弹出两个节点（注意顺序），成为字符的左右节点，再把字符节点压栈。
public TreeNode constructExpressionTree(String[] tokens) {
LinkedList<TreeNode> stack = new LinkedList<>();
for (String t : tokens) {
switch (t) {
case "+", "-", "*", "/" -> { // 运算符
TreeNode right = stack.pop();
TreeNode left = stack.pop();
TreeNode parent = new TreeNode(t);
parent.left = left;
parent.right = right;
stack.push(parent);
}
default -> { // 数字
stack.push(new TreeNode(t));
}
}
}
return stack.peek();
}
7.4.6 从前序与中序遍历序列构造二叉树
给定两个整数数组
preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
输入: preorder = [-1], inorder = [-1]
输出: [-1]
先通过前序遍历结果定位根节点（第一个肯定是根节点）
再结合中序遍历结果切分左右子树（根节点前是左子树，后面为右子树）
只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。
细节：
在中序遍历中对根节点进行定位时，一种简单的方法是直接扫描整个中序遍历的结果并找出根节点，但这样做的时间复杂度较高。我们可以考虑使用哈希表来帮助我们快速地定位根节点。对于哈希映射中的每个键值对，键表示一个元素（节点的值），值表示其在中序遍历中的出现位置。在构造二叉树的过程之前，我们可以对中序遍历的列表进行一遍扫描，就可以构造出这个哈希映射。在此后构造二叉树的过程中，我们就只需要
O(1)的时间对根节点进行定位了。
普通实现：
/**
* 根据前序中序遍历结果构造二叉树
*/
public class E09Leetcode105 {
/*
1
/ \
2 3
/ / \
4 6 7
preOrder = {1,2,4,3,6,7}
inOrder = {4,2,1,6,3,7}
根 1
pre in
左 2,4 4,2 （由pre得，父节点：2，结合in, 4为 2.left节点）
右 3,6,7 6,3,7 （pre第一个3 为父节点, 6 7分别为左右节点）
根 2
左 4
根 3
左 6
右 7
*/
public TreeNode buildTree(int[] preOrder, int[] inOrder) {
if (preOrder.length == 0) {
return null;
}
// 创建根节点
int rootValue = preOrder[0];
TreeNode root = new TreeNode(rootValue);
// 区分左右子树
for (int i = 0; i < inOrder.length; i++) {
if (inOrder[i] == rootValue) { // i 为 根节点 所在索引
// 0 ~ i-1 左子树
// i+1 ~ inOrder.length -1 右子树
int[] inLeft = Arrays.copyOfRange(inOrder, 0, i); // [4,2]
int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length); // [6,3,7]
// preLeft需要拷贝的数据长度与 inLeft一样 , inLeft是 0-i,那preLeft就是 1-i+1
int[] preLeft = Arrays.copyOfRange(preOrder, 1, i + 1); // [2,4]
int[] preRight = Arrays.copyOfRange(preOrder, i + 1, inOrder.length); // [3,6,7]
root.left = buildTree(preLeft, inLeft); // 2
root.right = buildTree(preRight, inRight); // 3
break; // 找到根节点 就不用继续for循环了
}
}
return root;
}
public static void main(String[] args) {
int[] preOrder = {1, 2, 4, 3, 6, 7};
int[] inOrder = {4, 2, 1, 6, 3, 7};
TreeNode root = new E09Leetcode105().buildTree(preOrder, inOrder);
}
}
以上代码力扣运行效率较低，代码可以进一步优化成下面
力扣官方题解：(递归＋哈希表)
public class Test08 {
private Map<Integer, Integer> indexMap; // key: inorder元素值, value: 索引
/**
*
* @param preorder
* @param inorder
* @param preorder_left 起始索引
* @param preorder_right 结尾索引
* @param inorder_left 起始索引
* @param inorder_right 结尾索引
* @return
*/
public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return null;
}
// 前序遍历中的第一个节点就是根节点（索引）
int preorder_root = preorder_left;
// 在中序遍历中定位根节点（索引）
int inorder_root = indexMap.get(preorder[preorder_root]);
// 先把根节点建立出来
TreeNode root = new TreeNode(preorder[preorder_root]);
// 得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
// 递归地构造左子树，并连接到根节点
// 先序遍历中「从 左边界+1（某个根节点的后一个） 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
// 递归地构造右子树，并连接到根节点
// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
// 构造哈希映射，帮助我们快速定位根节点
indexMap = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
indexMap.put(inorder[i], i);
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
}
7.4.7 从中序与后序遍历序列构造二叉树
后续遍历最后一个为根节点，跟上题一样，在中序遍历中找到根节点，前面左子树，后面右子树
代码模板与上题一样：
public class Test09 {
private HashMap<Integer, Integer> indexMap;
public TreeNode buildTree(int[] inorder, int[] postorder) {
indexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
indexMap.put(inorder[i], i);
}
return buildMyTree(inorder, postorder, 0, inorder.length - 1, 0, postorder.length -1);
}
private TreeNode buildMyTree(int[] inorder, int[] postorder, int in_left, int in_right, int post_left, int post_right) {
if (in_left > in_right) {
return null;
}
// 后续遍历最后一个为 root（父节点）
int rootValue = postorder[post_right];
// 定位inorderd的root索引
int in_rootIndex = indexMap.get(rootValue);
// 左子树长度
int left_tree_size = in_rootIndex - in_left;
// 建立根节点
TreeNode root = new TreeNode(rootValue);
root.left = buildMyTree(inorder, postorder, in_left, in_rootIndex - 1, post_left, post_left + left_tree_size - 1);
root.right = buildMyTree(inorder, postorder, in_rootIndex + 1, in_right, post_left + left_tree_size, post_right - 1);
return root;
}
}
Comments NOTHING