队列和栈-合集

（本系列是针对Leetcode上常见的队列和栈进行总结。）

1. 基础知识

• 在数组中，我们可以通过索引随机访问元素。但是，在某些情况下，我们可以想要限制处理的顺序。

• 这两种不同的顺序就是 ， 先入先出 先入后出 。以及两个相应的线性数据结构，队列和栈

• 在做到算法题的时候，队列一般用于BFS，而系统栈用于DFS

1.1 队列（先入先出）

• 在FIFO 数据结构中，将首先处理添加到队列的第一个元素。
• 如上图所示，队列是典型的FIFO的数据结构。插入(insert) 操作也称为入队（enqueue），新元素始终被添加到队列的末尾。删除（delete） 操作也被称为出队(dequeue) 。 你只能移除第一个元素。
• 总结：队尾入队，队首出队。

出队：

*入队 : *

1.1.1 数组实现队列

// 数组实现队列
public class MyQueue {
    // 1. 数组存放元素
    private List<Integer> data;

    // 2. 指向开始位置的指针
    private int p_start;

    // 3. 构造函数
    public MyQueue(){
        data = new ArrayList<Integer>();
        p_start = 0;
    }

    // 4. 入队
    public boolean enQueue(int x){
        data.add(x);
        return true;
    }

    // 5. 出队
    public boolean deQueue(){
        if (isEmpty() == true){
            return false;
        }
        
        // 出队相当于开始索引后移
        p_start ++;
        return true;
    }

    // 6. 获取队首元素
    public int getFront(){
        return data.get(p_start);
    }

    // 7. 判断队列是否为空
    public boolean isEmpty(){
        return p_start >= data.size();
    }

}

 class Main {
    public static void main(String[] args) {
        MyQueue q = new MyQueue();
        q.enQueue(5);
        q.enQueue(3);
        if (q.isEmpty() == false) {
            System.out.println(q.getFront());
        }
        q.deQueue();
        if (q.isEmpty() == false) {
            System.out.println(q.getFront());
        }
        q.deQueue();
        if (q.isEmpty() == false) {
            System.out.println(q.getFront());
        }
    }
}

缺点：

• 上面的实现很简单，但在某些情况下效率很低。 随着起始指针的移动，浪费了越来越多的空间。 当我们有空间限制时，这将是难以接受的。

• 让我们考虑一种情况，即我们只能分配一个最大长度为 5 的数组。当我们只添加少于 5 个元素时，我们的解决方案很有效。 例如，如果我们只调用入队函数四次后还想要将元素 10 入队，那么我们可以成功。
• 但是我们不能接受更多的入队请求，这是合理的，因为现在队列已经满了。但是如果我们将一个元素出队呢？

1.1.2 剑指 Offer 09. 用两个栈实现队列

题目描述：

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]


示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

遇到的问题

• 栈无法实现队列的功能：栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈
• 双栈可以实现列表的倒序：

设有含三个元素的栈 
A = [1,2,3] 和空栈 B = []。
若循环执行 A 元素出栈并添加入栈 B ，直到栈 A 为空，则 A = [] , B = [3,2,1]，即 栈 B 元素实现栈 A 元素倒序 。

• 利用栈B删除队首元素：倒序后，B执行出栈就相当于删除了A的栈底元素，即对应队首元素

class CQueue {
    LinkedList<Integer> A,B;


    public CQueue() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }
    
    public void appendTail(int value) {
        A.add(value);
    }
    
    public int deleteHead() {
        // 1. B不为空，说明已经完成了倒叙，直接返回B栈顶元素即可
        if (!B.isEmpty()){
            return B.poll();
        }else if (A.isEmpty()){
            // 2. 如果A为空,说明两个栈都为空
            return -1;
        }else {
            // 3. 说明两个栈都存在元素
            while (!A.isEmpty()){
                B.add(A.remove());
            }
            return B.remove();
        }
    }
}

具体的解析：在我的Leetcode专题里面有，所以这里不再过度阐述。

1.1.3 622. 设计循环队列

• 此前，我们提供了一种简单但低效的队列实现。（数组实现）
• 更有效的方法是使用循环队列，具体来说，我们可以使用固定大小的数组和两个指针来指示起始位置和结束位置。目的是重复使用被浪费的存储空间。

题目描述：

• 设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

• 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

• 你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

算法思路

• 这道题说“循环”的意思是要求我们在数组里实现。
• 在数组的操作中，我们参考“动态数组”的实现来完成。主要是为了让每一步操作的复杂度都降到最低。只不过我们自己实现动态扩容和缩容

注意：

1. 定义循环变量 front 和 rear 。一直保持这个定义，到底是先赋值还是先移动指针就很容易想清楚了。

   • front 队列头部第一个有效的位置
   • rear：指向队列尾部（即最后 1 个有效数据）的下一个位置，即下一个从队尾入队元素的位置。

2. 为了避免“队列为空”和“队列为满”的判别条件冲突，我们有意浪费了一个位置。

   • 浪费一个位置是指：循环数组中任何时刻一定至少有一个位置不存放元素。
   • 判断队列为空的条件 front == rear
   • 判断队列为满的条件 front == (rear + 1) % capacity (可以这样理解，当 rear 循环到数组的前面，要从后面追上 front，还差一格的时候，判定队列为满。)

3. 因为有循环的出现，要特别注意处理数组下标可能越界的情况。指针后移的时候，索引 + 1，并且要注意取模。

代码实现

//leetcode submit region begin(Prohibit modification and deletion)
class MyCircularQueue {
    private int front;
    private int rear;
    private int capacity;
    private int[] arr;

    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        // 浪费一个位置
        capacity = k + 1;
        arr = new int[capacity];

        front = 0; // 删除元素的时候，只索引 +1（注意取模）
        rear  = 0; // 插入元素的时候，先赋值，后索引 +1（注意取模）
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if (isFull()){
            return false;
        }
        // 先赋值，然后索引 + 1
        arr[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (isEmpty()){
            return false;
        }
        // 先索引 + 1即可
        front = (front + 1) % capacity;
        return true;
    }
    
    /** Get the front item from the queue. */
    public int Front() {
        if (isEmpty()){
            return -1;
        }
        return arr[front];
    }
    
    /** Get the last item from the queue. */
    public int Rear() {
        if (isEmpty()){
            return  -1;
        }
        return arr[(rear - 1 + capacity) % capacity];
    }
    
    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return rear == front;
    }
    
    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        // 经典设计
        return (rear + 1) % capacity == front;
    }
}

1.1.4 641. 设计循环双端队列

代码实现

//leetcode submit region begin(Prohibit modification and deletion)
class MyCircularDeque {
    // front == rear 队列为空
    // (rear + 1) == front 队列为满
    private int front;
    private int rear;
    private int[] arr;
    private int capacity;


    /** Initialize your data structure here. Set the size of the deque to be k. */
    public MyCircularDeque(int k) {
        capacity = k + 1;
        arr = new int[capacity];

        front = 0;
        rear = 0;
    }
    
    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    public boolean insertFront(int value) {
        if(isFull()) {
            return false;
        }
        // 索引 + 1 然后赋值
        front = (front - 1 + capacity) % capacity;
        arr[front] = value;
        return true;
    }
    
    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    public boolean insertLast(int value) {
        if (isFull()){
            return false;
        }
        arr[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }
    
    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    public boolean deleteFront() {
        if (isEmpty()){
            return false;
        }
        // front 是在数组的开头，同时防止数组越界
        front = (front + 1) % capacity;
        return true;
    }
    
    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    public boolean deleteLast() {
        if (isEmpty()){
            return false;
        }
        rear = (rear - 1 + capacity) % capacity;
        return true;
    }
    
    /** Get the front item from the deque. */
    public int getFront() {
        if (isEmpty()){
            return -1;
        }
        return arr[front];
    }
    
    /** Get the last item from the deque. */
    public int getRear() {
        if (isEmpty()){
            return -1;
        }
        // 当 rear 为0的时候防止数组越界
        // 因为真正的最后有效的元素是 rear - 1
        return arr[(rear - 1 + capacity) % capacity];
    }
    
    /** Checks whether the circular deque is empty or not. */
    public boolean isEmpty() {
        return front == rear;
    }
    
    /** Checks whether the circular deque is full or not. */
    public boolean isFull() {
        // 经典设计
        return (rear + 1) % capacity == front;
    }
}

2.1 栈（后入先出）

• 在 LIFO 数据结构中，将首先处理添加到队列中的最新元素。
• 与队列不同，栈是一个 LIFO 数据结构。通常，插入操作在栈中被称作入栈 push 。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop ，将始终删除队列中相对于它的最后一个元素。

2.1.1 栈的实现

• 栈的实现比队列容易。动态数组足以实现堆栈结构。这里我们提供了一个简单的实现供你参考：

public class MyStack {
    private List<Integer> list;

    public MyStack() {
        list = new ArrayList<Integer>();
    }

    public void push(int x){
        list.add(x);
    }

    public boolean isEmpty(){
        return list.isEmpty();
    }

    // 拿到栈顶元素
    public int top(){
        return list.get(list.size() - 1);
    }
    
    public boolean pop(){
        if (isEmpty()){
            return false;
        }
        list.remove(list.size() - 1);
        return true;
    }
}

2.1.2 155. 最小栈

题目描述：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) ——   将元素 x 推入栈中。
pop() ——     删除栈顶的元素。
top() ——     获取栈顶元素。
getMin() —— 检索栈中的最小元素。

示例：

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

Solution：辅助栈和数据栈同步

• 特点：编写简单，不需要考虑一些边界情况（缺点：可能会存储一些多余的元素）
• 规则如下：
  • 辅助栈为空的时候，必须放进来新的数字
  • 新来的数小于等于辅助栈栈顶元素的时候，才放入（这里“等于要考虑进去”，因为出栈的时候，相等的并且是最小值的元素要同步出栈），要不然就放入辅助栈栈顶自己
  • 出栈的时候，辅助栈的栈顶元素要等于数据栈栈顶的元素才出栈

总结：

• 出栈的时候，最小值出栈才同步
• 入栈的时候，最小值入栈才同步

public class MinStack {

    // 数据栈
    private Stack<Integer> data;

    // 辅助栈
    private Stack<Integer> helper;

    /**
     * initialize your data structure here.
     */

    public MinStack(){
        data =   new Stack<>();
        helper = new Stack<>();
    }

    // 思路1：数据栈和辅助栈在任何时候都要同步
    public void push(int x){
        data.add(x);
        if (helper.isEmpty() || helper.peek() >= x){
            helper.add(x);
        }else {
            helper.add(helper.peek());
        }
    }


    public void pop(){
        // 两个栈都需要pop操作
        if (!data.isEmpty()){
            helper.pop();
            data.pop();
        }
    }

    // 返回数据栈的栈顶
    public int top(){
        if (!data.isEmpty()){
            return data.peek();
        }
        throw new RuntimeException("栈元素为空");
    }

    // 返回最小栈的栈顶元素
    public int getMin(){
        if (!helper.isEmpty()){
            return helper.peek();
        }
        throw new RuntimeException("栈元素为空");
    }

}

复杂度分析：

• 时间复杂度：O(1) 栈的操作
• 空间复杂度：O(n) 需要一个辅助栈的空间

2.1.3 20. 有效的括号

题目描述

给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true

算法思路

• 栈的先入后出的特点和括号排序一致，即遇到左括号入栈，遇到右括号时将对应的栈顶元素左括号出栈，则遍历完所有括号之后stack 仍然为空。
• 建立哈希表存储所有左右括号的对应关系，（key 左括号， value 右括号）。这样查询2个括号是否对应只要O(1) 的时间复杂度；
  • 建立栈stack ，遍历字符串s并按照算法流程就行判断

算法流程

• 如果c 是左括号，则入栈push
  • 否则通过哈希表来判断对应关系，若stack 栈顶出栈的括号stack.pop() 与当前括号c不对应，则提前返回false

提前返回false

• 提前返回优点： 在迭代过程中，提前发现不符合的括号并且返回，提升算法效率。
  • 栈 stack 为空 ： 此时 stack.pop()会报错，因此使用一个取巧的办法，给stack 赋一个初值 ？ ， 并在哈希表中建立 ？ 和 ？ 的对应关系。此时当stack 为空且c 是右括号的时候，可以正常提前返回false.
  • 字符串s 以左括号结尾： 这种情况下，可以正常的遍历完字符串，但是最后的左括号遗留了下来，这时候要判断最后栈的长度是不是等于1，如果等于，说明多出来一个左括号，不是有效的括号组合。

class Solution {
    public boolean isValid(String s) {
        // map来预存括号以及辅助判断字符
        Map<Character, Character> map = new HashMap<>();
        map.put('{','}');
        map.put('[',']');
        map.put('(',')');
        map.put('?','?');

        // 没有左括号直接返回false
        if (s.length() > 0 && !map.containsKey(s.charAt(0))){
            return false;
        }

        // 栈
        LinkedList<Character> list = new LinkedList<>();
        list.add('?');

        // 遍历字符串，检查括号符不符合要求
        char[] chars = s.toCharArray();
        for (char c : chars) {
            // 左括号放入栈中
            if (map.containsKey(c)){
                list.add(c);
            }else if (map.get(list.removeLast()) != c){
                // 栈顶左括号和右括号是否匹配
                return false;
            }
        }
        // 最后判断有没有遗留左括号
        return list.size() ==  1;
    }
}

• 复杂度分析
  • 时间复杂度 O(N)：正确的括号组合需要遍历 1 遍 s；
  • 空间复杂度 O(N)：哈希表和栈使用线性的空间大小。

2.1.4 739. 每日温度

题目描述：

本质 ： 找到数组中第一个大于该元素数字的索引 ，并返回索引差值

根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是[1, 30000]。每个气温的值的均为华氏度，都是在[30, 100]范围内的整数。

解法思路：单调递减栈

class Solution {
    public int[] dailyTemperatures(int[] T) {
        // 单调递减栈
        Stack<Integer> stack = new Stack<>();
        // 结果集
        int[] ret = new int[T.length];

        for (int i = 0; i < T.length; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int idx = stack.pop();
                ret[idx] = i - idx;
            }
            // 栈为空的话
            stack.push(i);
        }
        return ret;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是温度列表的长度。正向遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作。
• 空间复杂度：O(n)，其中 n是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。

2.1.5 150. 逆波兰表达式求值

题目描述

根据 逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

• 整数除法只保留整数部分。
• 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

示例 1：

输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：

输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：

输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释: 
该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

方法：单调栈

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        // 减少自动装箱拆箱的负担
        Integer op1,op2;

        // 遍历字符串，进行运算
        for (String s : tokens) {
            switch (s){
                case "+" :
                    op2 = stack.pop();
                    op1 = stack.pop();
                    stack.push(op1 + op2);
                    break;
                case "-":
                    op2 = stack.pop();
                    op1 = stack.pop();
                    stack.push(op1 - op2);
                    break;
                case "*":
                    op2 = stack.pop();
                    op1 = stack.pop();
                    stack.push(op1 * op2);
                    break;
                case "/":
                    op2 = stack.pop();
                    op1 = stack.pop();
                    stack.push(op1 / op2);
                    break;
                default:
                    stack.push(Integer.valueOf(s));
                    break;
            }
        }
        // 返回最后栈顶元素
        return stack.pop();
    }
}

2. 队列和BFS

2.1 BFS

• 广度优先搜索（BFS）是一个常见应用是从根节点到目标节点的最短路径。

• 在本文中，我们提供了一个示例来解释在 BFS 算法中是如何逐步应用队列的。

分析

1. 节点的处理顺序是什么？

• 在第一轮中，我们处理根节点。
• 在第二轮中，我们处理第二层节点。
• 第三轮中，我们处理第三层节点。
• 。。。。

• 与树的层序遍历类似，越是接近根结点的结点将越早地遍历。

2. 队列的入队和出队顺序是什么？

• 首先将根节点入队，逐个处理已经在队列中的节点，并将所有的邻居添加到队列中。值得注意的是，新添加的节点并不会立即遍历，而是在下一轮搜索中处理。
• 节点处理的顺序和添加到队列的顺序是完全相同的，即先进先出（FIFO）,这就是我们为什么使用队列的原因。

2.2 BFS两种模板

• 之前，我们已经介绍了使用 BFS 的两个主要方案：遍历或找出最短路径。通常，这发生在树或图中。正如我们在章节描述中提到的，BFS 也可以用于更抽象的场景中。

模板一：

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                add next to queue;
            }
            remove the first node from queue;
        }
    }
    return -1;          // there is no path from root to target
}

• 每一轮中，队列的节点是等待处理的节点
• 在每个更外的一层while 循环之后，我们举例根节点更远一步。变量step 从根节点到我们正在访问的节点的距离。

模板二

• 有时候，确保我们永远不会访问同一个节点两次很重要。
• 否则的话，我们可能会陷入无限死循环，如果是这样，我们可以添加一个哈希set来解决这样的问题，下面是修改后的伪代码：

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路
    
    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

• 队列q 就不用说了，BFS核心的数据结构；
• cur.adj() 表示 cur 相邻的节点，比如说二维数组中，cur 的上下左右位置就是相邻的节点；
• visited() 节点的作用就是防止走回头路
  • 大部分情况下，visited 数组或者说 哈希表 是必须的
  • 但是像二叉树一般的结构，没有子节点到父节点的指针，不会走回头路就不需要visited

2.3 BFS 题目1： 102. 二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

[
  [3],
  [9,20],
  [15,7]
]

思路：BFS

给定一个二叉树，返回其按层序遍历得到的节点值。 层序遍历即逐层地、从左到右访问所有结点。

class Solution{
    public List<List<Integer>> levelOrder(TreeNode root){
        // res 记录最后结果
        List<List<Integer>> result = new LinkedList<>();

        // 特判
        if (root == null){
            return result;
        }

        // 队列（LinkedList实现）
        Queue<TreeNode> queue = new LinkedList<>();

        // 根节点放入队列
        queue.add(root);


        while(!queue.isEmpty()){
            List<Integer> subList = new LinkedList<>();

            int curSize = queue.size();
            for (int i = 0; i < curSize; i++) {
                // 取出队列首元素并删除
                TreeNode curr = queue.poll();
                if (curr != null){
                    // 队首元素放到结果中
                    subList.add(curr.val);
                    // 对子节点进行处理
                    if (curr.left != null){
                        queue.add(curr.left);
                    }
                    if (curr.right != null){
                        queue.add(curr.right);
                    }
                }
            }
            result.add(subList);
        }
        return result;
    }
}

• 可以看到，在 while 循环的每一轮中，都是将当前层的所有结点出队列，再将下一层的所有结点入队列，这样就实现了层序遍历。

复杂度分析

记树上所有节点的个数为 nn。

• 时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。
• 空间复杂度：队列中元素的个数不超过 nn 个，故渐进空间复杂度为 O(n)。

2.4 BFS 题目2：111. 二叉树的最小深度

题目描述

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

  3
 / \
9  20
  /  \
 15   7

思路：BFS

• 首先来看看DFS和BFS的区别

• 这个遍历顺序也是 BFS 能够用来解「层序遍历」、「最短路径」问题的根本原因。

2.5 BFS 题目3 ： 279-完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.
示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

解法：BFS（下面一图胜千言）

class Solution {
    public int numSquares(int n) {
        Queue<Integer> queue = new LinkedList<>();
        HashSet<Integer> visited = new HashSet<>();
        int level = 0;
        queue.add(n);
        while (!queue.isEmpty()) {
            int size = queue.size();
            level++; // 开始生成下一层
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                //依次减 1, 4, 9... 生成下一层的节点
                for (int j = 1; j * j <= cur; j++) {
                    int next = cur - j * j;
                    if (next == 0) {
                        return level;
                    }
                    if (!visited.contains(next)) {
                        queue.offer(next);
                        visited.add(next);
                    }
                }
            }
        }
        return -1;
    }
}

3. 栈和DFS

• 正如我们在本章的描述中提到的，在大多数情况下，我们在能使用 BFS 时也可以使用 DFS。但是有一个重要的区别：遍历顺序。

• 与 BFS 不同，更早访问的结点可能不是更靠近根结点的结点。因此，你在 DFS 中找到的第一条路径可能不是最短路径。

• 在本文中，我们将为你提供一个 DFS 的递归模板，并向你展示栈是如何帮助这个过程的。

模板

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

3.1 94. 二叉树的中序遍历

给定一根二叉树，返回它的中序遍历

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

class Solution{
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();
        helper(root,res);
        return res;
    }

    private void helper(TreeNode root, List<Integer> res) {
        // 判断当前是否是null
        if (root != null){
            // 1. 左子树
            if (root.left != null){
                helper(root.left,res);
            }
            // 2. 打印
            res.add(root.val);
            // 3. 右子树
            if (root.right != null){
                helper(root.right,res);
            }
        }
    }
}

前序遍历：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        DFS(root,res);
        return res;
    }


    private void DFS(TreeNode root,List<Integer> res){
        if(root != null){
            res.add(root.val);

            if(root.left != null){DFS(root.left,res);}

            if(root.right != null){DFS(root.right,res);}
        }
    }
}

后序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        DFS(root,res);
        return res;
    }


    private void DFS(TreeNode root,List<Integer> res){
        if(root != null){
            if(root.left != null){DFS(root.left,res);}

            if(root.right != null){DFS(root.right,res);}

            res.add(root.val);
        }
    }
}

3.3 329. 矩阵中的最长递增路径

打赏