「优先队列」专题 3:索引堆


「队列」专题 3:索引堆

索引堆是一个相对于普通堆更加高级的数据结构。

为什么要引入索引堆这个数据结构?

在一些场景下,堆这个数据结构不高效,或者说功能不够用:

1、如果元素是非常复杂的结构(例如是长字符串),交换这件事情会产生大量的性能消耗;

我们之前在堆中的操作有大量地交换操作,这种直接交换内存的操作,在元素占用内存比较小的时候,并没有多少性能的消耗,但是当须交换位置的元素占用内存很大的时候,此时交换两个元素的内存就不可以被忽视,于是,我们就想通过给堆中的每个元素映射一个标识,也就是我们这一节提到的索引。通过索引的操作来实现元素的操作。

通过索引可以找到我们真正存放在数组中的元素,而索引所代表数据构成一个最大堆。

举一个可能不是很恰当的生活中的例子,我们要给一组学生按照身高进行排序,我们不用把他们全部喊出来让他们从矮到高排好,我们只要让他们报上自己的身高,在纸上做他们身高的比较就可以了。

2、元素位置发生改变以后,很难再次索引到它,例如:我们想要将原来索引是 $6$ 的元素的优先级提升或者下降一下,但是我们不知道原来索引是 $6$ 的元素到底是谁了。

想一想为什么没有索引就不能支持 change,因为索引不到原来的数据,因此我就不知道要 change 哪个数据,除非遍历一遍整个数组元素。

在实际应用中,我们除了有 insertextract 这两个操作以外,我们数组中的元素很可能是动态变化的,在变化的过程中,如何保持最大堆的性质,这就是我们要讨论的问题。在以后章节的学习中,我们将会看到 change 操作的实际应用。

我们不交换数据,而给每个数据一个索引,索引代表的数据是堆有序的。即:我们比较的是数据,交换的是索引。

最大索引堆

索引堆的思想类似于在医院看病使用的“叫号排队”机制,想想我们去医院挂号排队的时候:我们不用真的站在那里排成一队,每个人领一个号坐在大厅里,轮到你了,你才进去看病。

最大索引堆的内部维护了一个索引数组,这个索引数组所代表的数据构成了一个最大堆;由于索引和堆中数据存在一一对应的关系,我们通过索引可以很快地定位到数据,而索引的操作又是十分方便的。

下面以最大索引堆为例,阐述相关的技巧和思想:

最大索引堆中的 data 数组是由用户定义的,用户的 insertextract、和 change 操作只会插入、取出和修改 data 数组中的元素,由程序员来维护内部的索引数组,索引数组堆有序。

1、比较的时候使用 data 数组进行比较,交换的时候交换的是 indexes 数组的元素;

2、比较的是 data 的数据,交换的是 indexes 的位置

下面,我们看一个例子,我们浪费一个元素的位置。下面这张表是数组原始的样子:

0 1 2 3 4 5 6 7 8 9 10
indexes (空着) 1 2 3 4 5 6 7 8 9 10
data (空着) 15 17 19 13 22 16 28 30 41 62

heapify 以后,data 元素不动,indexes 替换成它们代表的元素的值以后,就是一个最大堆

0 1 2 3 4 5 6 7 8 9 10
indexes 10 9 5 7 8 6 2 4 3 1
data 15 17 19 13 22 16 28 30 41 62

说明:indexes[1] = 10 ,表示 data[10] 在最大堆中的位置是 1 ,抽象成一般情况就是:indexes[x] = i ,表示 data[i] 在最大堆中的位置是 x 。紧扣索引数组是堆有序这一点就不难理解了。

索引堆-1

我们可以通过对之前最大堆的数据结构的改造,修改成一个最大索引堆。首先修改构造函数,引入索引数组。

Python 代码:

class IndexMaxHeap:
    def __init__(self, capacity):
        self.data = [None for _ in range(capacity + 1)]
        # 初值设置为 0 ,表示该位置还没有放置元素
        self.indexes = [0 for _ in range(capacity + 1)]
        self.count = 0
        self.capacity = capacity

其次修改 insert 方法:这里的 insert 虽然指定了索引,但是一定是在 data 数组的最后添加数据。我们插入一个元素的时候,同时要指定这个元素的索引 i ,这里要注意:传入的 i 对用户而言是从 $0$ 开始的,因此在底层发生操作之前,得先加 $1$。

Python 代码:

# 此时 insert 要给一个索引位置
def insert(self, i, item):
    if self.count + 1 > self.capacity:
        raise Exception('堆的容量不够了')
        i += 1
        self.data[i] = item
        # 这一步很关键,在内部索引数组的最后设置索引数组的索引
        self.indexes[self.count + 1] = i
        self.count += 1
        self.__shift_up(self.count)

shift_up 方法也要修改:这里就是我们上面说的那一点:比较的是 data 的数据,交换的是 indexes 的位置

Python 代码:

def __shift_up(self, k):
    # 比较的时候,上面套一层 indexes,交换的是 indexes
    while k > 1 and self.data[self.indexes[k // 2]] < self.data[self.indexes[k]]:
        self.indexes[k // 2], self.indexes[k] = self.indexes[k], self.indexes[k // 2]
        k //= 2

然后修改 extract_max 方法:

Python 代码:

def extract_max(self):
    if self.count == 0:
        raise Exception('堆里没有可以取出的元素')
        # 里面套一层 indexes
        ret = self.data[self.indexes[1]]
        # 交换的是索引
        self.indexes[1], self.indexes[self.count] = self.indexes[self.count], self.indexes[1]
        self.count -= 1
        self.__shift_down(1)
        return ret

Python 代码:

def __shift_down(self, k):
    while 2 * k <= self.count:
        j = 2 * k
        # 比较的是 data ,交换的是 indexes
        if j + 1 <= self.count and self.data[self.indexes[j + 1]] > self.data[self.indexes[j]]:
            j = j + 1
            if self.data[self.indexes[k]] >= self.data[self.indexes[j]]:
                break
                self.indexes[k], self.indexes[j] = self.indexes[j], self.indexes[k]
                k = j

最后实现 change 方法:为了维持堆的性质,我们应当尝试向上挪一下 shift up,向下挪一下 shift down。关键在于找到用户认为的那个数据,在索引数组中是第几位,针对这个位置进行下沉和上移,即找到一个 j 满足:indexes[j] = ij 表示 data[i] 在堆中的位置,之后 shift up(j),然后 shift down(j)。还是紧扣那一点:比较的是 data ,交换的是 indexes

Python 代码:

def change(self, i, new_item):
    # 把用户视角改成内部索引
    i += 1
    self.data[i] = new_item

    # 重点:下面这一步是找原来数组中索引是 i 的元素
    # 在索引数组中的索引是几,这是一个唯一值,找到即返回
    # 优化:可以引入反向查找技术优化
    for j in range(1, self.count + 1):
        if self.indexes[j] == i:
            self.__shift_down(j)
            self.__shift_up(j)
            return

说明: change 这个函数是可以进行优化的,通过引入反向查找数组来进行优化。反向查找的作用,就是帮助我们寻找原来索引的位置,在最大堆中是几。这个操作也叫“反向查找”,是一个基础且常见的技巧。

索引堆的优化:反向查找

我们引入了反向查找表。这一节的内容和思想很重要,要多看。reverse[i] 表示索引 iindexes(堆)中的位置。引入 reveres 数组的意义是,可以在执行 change 这个方法的时候,可以通过 $O(1)$ 时间复杂度查询到用户认为索引是 i 的元素,在索引数组组成的堆中的索引是几。

注意:为 reverse 数组赋初始值,$0$ 有特殊的含义:reverse[i] = 0 表示 data[i] 未赋值。

我们在捋一遍:引入反向查找是为了“找到 indexes 数组中原来索引是 i 的元素的位置”,即 reverse[i] = j 表示 data[i] 在索引堆中的位置是 j

通过引入反向查找数组,实现反向查找 indexes 数组中,原来为第 i 号的那个元素排在了 indexes 数组的第几位,通过对 reverse 数组的维护,使得 change 操作时间复杂度降到了 $O(1)$。

reverse[i] 表示原来第 i 个数在 indexes 数组中的位置。

根据 reverse 数组反向查找的意义,我们很容易得到:如果 indexes[i] = j,那么 reveres[j] = i,可以看出来,“反向查找”有点“反函数”的意思。

indexes[i] = j 代入 reveres[j] = i ,得 reveres[index[i]] = i

reveres[j] = i 代入 indexes[i] = j ,得 indexes[reveres[j]] = j

这也就是“反函数的反函数是自己”。利用上述两个性质可以实现反向查找。

注意: reveres 数组的概念其实并不难理解,大家只要把 reveres 这个数组自己填一下就会非常清楚了。

0 1 2 3 4 5 6 7 8 9 10
data 15 17 19 13 22 16 28 30 41 62
indexes 10 9 5 7 8 6 2 4 3 1
reverse 10 7 9 8 3 6 4 5 2 1

说明:indexes[1] = 10,表示使用者认为的第 $10$ 号数据,在 indexes 数组中的索引是 $1$,故 reverse[10] = 1

indexes[2] = 9,表示使用者认为的第 $9$ 号数据,在 indexes 数组中的索引是 $2$,故 reverse[9] = 2

indexes[3] = 5,表示使用者认为的第 $5$ 号数据,在 indexes 数组中的索引是 $2$,故 reverse[5] = 3

因此,reverse 数组的作用就是:通过使用者认为的索引编号,快速找到它在 indexes 数组形成的堆中的位置

维护reverse 数组要注意的事项:在 indexes 数组交换位置的时候,reverse 数组也要同步交换。

下面我们来分析一下 indexes 数组如果交换了位置,reverse 数组要如何交换。

假如要交换 indexes 数组 34 的位置,由于此时 indexes[3] = 7indexes[4] = 5 ,为了保证 reverse 数组的正确性,(我们暂时不去看表),就应该使得 reverse[7] = 3reverse[5] = 4

此时再去看表, reverse[7] = 4reverse[5] = 3。怎么交换的,就很清楚了。reverse 数组是 indexes 数组映射以后的两个值交换。

索引堆的应用

实现多路归并排序

这部分的知识我是在参考资料1(《算法》(第4版)P204)中看到的。在这里做一个笔记。索引堆只存了 3 个元素,索引堆不仅仅把我们要的那个数据拿出来了,并且还给出了这个数据在使用者眼里的索引的位置

图论中使用索引堆找到最小生成树

本文源代码

Python:代码文件夹,Java:代码文件夹

参考资料

1、图书《算法》(第4版), Algorithms Fourth Edition,作者:[美] Robert Sedgewick,[美] Kevin Wayne 著,谢路云 译,图书配套网站

2、慕课网 liuyubobobo 老师《算法与数据结构》课程以及对应的 GitHub 代码仓库

3、慕课网 liuyubobobo 老师《看得见的算法》课程以及对应的 GitHub 代码仓库

4、【多说两句】关于索引堆中的索引和数据

https://coding.imooc.com/learn/questiondetail/4945.html。

(本节完)


索引堆是一个比较有意思的数据结构。索引技术其实还是满常见的,听起来比较高大上,其实就是做了一个对应关系。

堆排序和 Heapify

什么是基础堆排序

我们的排序工作就描述如下:把待排序数组按顺序放入一个堆(入队),全部放入以后,然后再从堆中出队,每次出队的元素就是当前数组中最大的元素,于是我们可以倒着赋值回去,直到堆中没有元素(此时原始数组也被赋值“满”了)时,就能得到一个升序的数组。

Java 代码:

全部放入优先队列,再一个一个取出,倒着放即可:

import java.util.Arrays;

public class HeapSort {

    // 我们之前实现的 MaxHeap 这个数据结构,把它作为成员变量,利用它来完成排序
    private MaxHeap maxHeap;

    public HeapSort() {
        this.maxHeap = new MaxHeap(20);
    }

    public HeapSort(int capacity) {
        this.maxHeap = new MaxHeap(capacity);
    }

    // 把数组中的元素先全部挨个 insert 到最大堆中
    // 然后在依次取出,因为每次取出的都是剩下的元素中的最大者
    // 因此应该倒着覆盖到原待排序数组
    public void sort(int[] nums) {
        int[] temp = nums.clone();
        for (Integer item : temp) {
            maxHeap.insert(item);
        }
        while (maxHeap.getSize() > 0) {
            nums[maxHeap.getSize() - 1] = maxHeap.extractMax();
        }
    }

    public static void main(String[] args) {
        int[] nums = {8, 1, 4, 6, 3, 2, 5, 9, 7};
        HeapSort heapSort = new HeapSort(nums.length);
        heapSort.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

最大堆的第 3 个重要操作:heapify

什么是 heapify

在上一步“堆排序”中,我们注意到,有这样一个操作“把待排序数组按顺序放入一个堆(入队)”,这一步得一个接着一个按照顺序放入堆中,那么我们有没有一个神一样的操作,直接把一个数组丢给一个“堆”(此时还不能称为“堆”,只能说是把一个数组丢给一个堆的构造方法),让这个数组自行调整成一个最大堆,那么这个操作就叫 heapify。

因此 heapify 就是尝试将一整个数组构建成一个堆的更好的方式,因为此时无需借助额外的空间就完成了最大堆的构建,并且我们只需对数组中一半的元素执行 shift down 就可以了。

首先,我们直接把一个数组传到 MaxHeap 的构造方法里,通过从 length / 2 索引到索引 1 ,逐个执行 shift down 操作就使得了此时的数组成为了最大堆

Java 代码:

public MaxHeap(int[] arr) {
    int length = arr.length;
    data = new int[length + 1];
    for (int i = 0; i < length; i++) {
        data[i + 1] = arr[i];
    }
    count = length;
    // heapify:通过从 length / 2 索引到索引 1 ,逐个执行 shift down 操作就使得了此时的数组成为了最大堆
    for (int i = length / 2; i >= 1; i--) {
        shiftDown(i);
    }
}

注意:heapify 的操作只有 shift down。

那么为什么没有 shift up 呢?我是这样认为的:shift up 是认为”上面”的元素可能不对,所以要将当前考虑的元素尝试上移。shift down 是认为”下面”的元素可能不对,所以要将当前考虑的元素直至根节点逐个尝试下移。

heapify 后挨个取出来,倒着放回待排序数组就可以了。

import java.util.Arrays;

public class HeapSort2 {

    private MaxHeap maxHeap;

    public HeapSort2(int[] arr) {
        this.maxHeap = new MaxHeap(arr);
    }

    public void sort(int[] nums) {
        while (maxHeap.getSize() > 0) {
            nums[maxHeap.getSize() - 1] = maxHeap.extractMax();
        }
    }

    public static void main(String[] args) {
        int[] nums = {8, 1, 4, 6, 3, 2, 5, 9, 7};
        HeapSort2 heapSort2 = new HeapSort2(nums);
        heapSort2.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

原地堆排序

原地堆排序的基本思路

注意:在这一小节中,我们要转换一下脑筋,我们要使用原地堆排序,就是不想借助额外的空间,那么拿到的数组一定 0 号位置是有数值的,所以,我们要实现的算法必须基于 0 号位置存放元素来实现。

我们在上一节也可以看到,我们将一个数组通过 heapify 即 shift down 的方式逐渐地整理成一个最大堆。

其实,原地堆排序这个想法是非常直观的,从 shift down 的操作我们就可以得到启发,堆中最大的那个元素在数组的 0 号索引位置,我们把它与此时数组中的最后一个元素交换,那么数组中最大的元素就放在了数组的末尾,此时再对数组的第一个元素执行 shift down,那么 shift down 操作都执行完以后,数组的第 1 个元素就存放了当前数组中的第 2 大的元素。

可能以上这样说,并不是很严谨,但我想思路已经说得很清楚了。

代码实现的注意事项

  • 此时最大堆中数组的索引从 $0$ 开始计算。与之前索引从 $1$ 开始的最大堆实现比较,性质就发生了变化,但并不会不好找,我们可以自己在纸上画一个完全二叉树就可以很清晰地发现规律:${\rm parent}(i)=\cfrac{i-1}{2}$,${\rm left \quad child}(i) = 2 \times i +1$,${\rm right \quad child}(i) = 2 \times i +2$,最后一个非叶子结点的索引是:$\cfrac{count-1}{2}$;

  • 原地堆排序,因为索引从 0 号开始,相应的一些性质在索引上都发生变化了,为此,需要重新实现一下,但并不需要重新实现 MaxHeap 里所有的方法;

  • 注意到我们只有 shift down 的操作,对于 shift down 的实现,一些细节就要很小心,shift down 是在一个区间内进行的,这个区间的端点,应该成为我们新设计的 shift down 方法的实现。

Java 代码:

import java.util.Arrays;

public class HeapSort3 {

    /**
     * 原地堆排序的目标就是,不再借助 MaxHeap 这个数据结构进行排序,减少了空间复杂度
     * 注意:此时我们的数组索引从 0 开始定义(自己在纸上画一下图,就能清晰地明白算法实现的含义)
     *
     * @param arr 待排序数组
     */
    public void sort(int[] arr) {
        int length = arr.length;
        // 首先 heapify:将一个无序的数组组成了一个最大堆,第 1 个元素就是最大值
        for (int i = (length - 1) / 2; i >= 0; i--) {
            shiftDown(arr, length, i);
        }
        for (int i = length - 1; i > 0; i--) {
            swap(arr, 0, i);
            shiftDown(arr, i, 0);
        }
    }

    // 注意 shiftDown 不能复用我们上面写的,而设计成
    // 对 0 开始,end 为止,即将 arr 中 [0,end] 部分的数组元素视为"最大堆"
    // 对索引为 i 的元素进行 shift down 的操作
    private void shiftDown(int[] arr, int end, int i) {
        // 如果有右孩子的节点,并且右孩子节点比左孩子节点的值要大
        // 此时可以忽略左孩子节点的存在,拿右孩子节点的数值和自己比较
        // 只要它有左孩子,就不是叶子节点,就可能 shift down,注意:这里是小于号
        while (2 * i + 1 < end) {
            int k = 2 * i + 1;
            if (k + 1 < end && arr[k] < arr[k + 1]) {
                k = k + 1;
            }
            if (arr[i] < arr[k]) {
                swap(arr, i, k);
                i = k; // 留意
            } else {
                break;
            }
        }
    }

    private void swap(int[] arr, int index1, int index2) {
        if (index1 == index2) {
            return;
        }
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {8, 1, 4, 6, 3, 2, 5, 9, 7};
        HeapSort3 heapSort3 = new HeapSort3();
        heapSort3.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

索引堆

为什么要引入索引堆这个数据结构?

在堆的一些操作过程中,不论是 insert 还是 extractMax 方法,都涉及了一些元素的交换操作,交换数组中的元素的位置,在一些场景下性能消耗很大。因此,我们可以在堆的内部实现一个索引数组,通过索引可以找到我们真正存放在数组中的元素,而索引所代表数据构成一个最大堆。这就是我们要引入索引堆的原因。

我们举一个可能不是很贴切的生活中的例子,我们要给一组学生按照身高进行排序,我们不用把他们全部喊出来让他们从矮到高排好,我们只要让他们报上自己的身高,在纸上做他们身高的比较就可以了。

我还想到一点:现在我们都进入了移动支付时代,我们购买物品不需要把真真实实的钱给商家,这种操作就很像我们引入索引堆的操作,我们通过1、自己账户上的钱减少2、商家用户账上的钱增多,这种方式实现了转账,给我们的生活带来了巨大的方便。一手交钱一首交货的时代已经不存在了,我们只会看到快递小哥把货送到你家,而不会有快递小哥把你的钱寄给卖家。相信很多人像我一样,出门带的现金已经很少很少了,甚至有些时候,我们出门根本可以不带钱。

  • 实现要点:

1、引入一个 indexes 数组;

2、比较的时候,使用 indexs 所对应的 data 来进行比较,交换的是 index 的位置,我们内部的实现仍然从 1 号索引开始存放数据,但这一点对外部用户来说是不可知的;

对于我们索引堆的使用者来说,他们只需要知道,这是一个数据结构,可以往里面存入数据,而每一次那出来的数据,都是当前已经存放在这个数据结构中最大的那个元素。

3、我们完全可以直接使用我们之前实现的 MaxHeap 来实现最大堆。

  • 索引堆要支持的操作: 在实现的时候,要注意 insert(i,item) 的实现,不是任意位置的 i都可以 insert 的,一般有两种情况:1、insert 到使用者所认为的优先队列的尾部;2、insert 到刚刚出队的那个元素的位置,因为那个位置的数据“已经没有了”,这一点要好好体会
shiftUp(int k) 将位于 indexes 数组中的索引为 k 的元素逐个上移。
shiftDown(int k) 将位于 indexes 数组中的索引为 k 的元素逐个下。
insert(i,item) 特别注意:这里的 i 是由使用者保证的,是业务相关的,不能完全从程序和语法的角度来判断 i 的合理性。
extractMax() 将此时二叉堆中的最大的那个数据返回。
extractMaxIndex() 将此时二叉堆中的最大的那个数据对应的索引返回。
getItem(int i) 获得索引为 i 的数据,通常这个数据是刚刚出队的索引,是由 extractMaxIndex() 方法来的。
change(int i,int item) 修改索引为 i 的数据的“优先级”。

【多说两句】关于索引堆中的索引和数据

https://coding.imooc.com/learn/questiondetail/4945.html

索引堆的优化

索引堆的优化方法

我们想找一找在使用者认为的优先队列中指定索引的数据,在我们的 indexes 数组中,排在第几位,我们使用了遍历,这种做法效率是不高的。

Java 代码:

for (int j = 1; j <= count; j++) {
    if (indexes[j] == i) {
        // 找到了 j
        shiftDown(j);
        shiftUp(j);
        return;
    }
}

我们可以通过引入一个反向查找数组,实现反向查找 indexes 数组中,值为 i 的那个元素排在了 indexes 的第几位,通过对 reverse 数组的维护,就使得我们对反向查找这件事情的时间复杂度降到了 $O(1)$。

  • reverse[i] 表示索引 i 在 indexes(堆)中的位置。引入 reveres 数组的意义是,可以在执行 change 这个方法的时候,使用 O(1) 这个时间复杂度,直接找到。
  • reverse 数组的性质:

性质1:如果 indexes[i] = j,那么 reveres[j] = i

性质2:indexes[reveres[i]] = ireveres[index[i]] = i

  • reveres 数组的概念其实并不难理解,大家只要把 reveres 这个数组自己填一下就会非常清楚了。
0 1 2 3 4 5 6 7 8 9 10
data 15 17 19 13 22 16 28 30 41 62
indexes 10 9 5 7 8 6 2 4 3 1
reverse 10 7 9 8 3 6 4 5 2 1

怎么看这张表:

indexes[1] = 10,表示使用者认为的第 10 号数据,排在了优先队列的第 1 位,即 10 这个数字在 indexes 数组中的索引是 1,故 revers[10] = 1;

indexes[2] = 9,表示使用者认为的第 9 号数据,排在了优先队列的第 9 位,即 9 这个数字在 indexes 数组中的索引是 2,故 revers[9] = 2;

indexes[5] = 8,表示使用者认为的第 8 号数据,排在了优先队列的第 5 位,即 8 这个数字在 indexes 数组中的索引是 5,故 revers[8] = 5;

所以,revers 数组的作用就是:通过使用者认为的索引数据,它在 indexes 数组形成的堆中的位置

  • reverse 数组在 indexes 数组交换位置的时候,应该如何维护

下面我们来分析一下 indexes 数组如果交换了位置,reverse 数组要如何交换位置。

假如要交换 indexes 数组 3 和 4 的位置,那么此时 indexes[3] = 7 ,indexes[4] = 5 ,为了保证 reverse 数组的正确性,(我们暂时不去看表),就应该使得 reverse[7] = 3,reverse[5] = 4。

此时再去看表, reverse[7] = 4,reverse[5] = 3。怎么交换的,就很清楚了。reverse 数组是 indexes 数组映射以后的两个值交换。

索引堆的应用

  • 实现多路归并排序

这部分的知识我是在参考资料1(《算法》(第4版)P204)中看到的。在这里做一个笔记。索引堆只存了 3 个元素,索引堆不仅仅把我们要的那个数据拿出来了,并且还给出了这个数据在使用者眼里的索引的位置

  • 图论中使用索引堆找到最小生成树

参考资料


文章作者: liwei
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liwei !
评论
 上一篇
「力扣」第 103 题:二叉树的锯齿形层次遍历(中等) 「力扣」第 103 题:二叉树的锯齿形层次遍历(中等)
「力扣」第 103 题:二叉树的锯齿形层次遍历(中等)传送门:103. 二叉树的锯齿形层次遍历。 给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 例如:给定二叉树
下一篇 
「力扣」第 102 题:二叉树的层次遍历 「力扣」第 102 题:二叉树的层次遍历
「力扣」第 102 题:二叉树的层次遍历传送门:102. 二叉树的层次遍历。 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如:给定二叉树: [3,9,20,null,null,15,7], 3 /
  目录