专栏首页golang+php层序遍历?套模板就够了

层序遍历?套模板就够了

学算法认准 GTAlgorithm,点击下方卡片即可搜索:

1.树的层序遍历

顾名思义,对于树型结构,层序遍历就是按层从上到下,每层按一定顺序对树的节点进行遍历。我们通过如图所示的二叉树进行说明:对于左边的二叉树,按层划分后可得到右边的分层结构。

二叉树及其层序遍历示意图

如果按照每层从左到右的遍历逻辑,这棵二叉树的层序遍历序列就是

[1, 4, 2, 7, 20, 5]

。通过代码如何实现呢?一般地,我们利用队列

queue

作为容器,按照如下逻辑进行遍历:

// 0. 声明队列
queue<TreeNode*> q;
// 1. 将根节点加入队列
q.push(root);
// 2. 遍历队列中每个节点
while(!q.empty()) {
    TreeNode* cur = q.front();
    q.pop();
    // 3. 记录当前节点值
    vec.push(cur->val);
    // 4. 将左右孩子放入队列
    q.push(cur->left);
    q.push(cur->right);
}

同一层中的节点自左向右遍历是通过队列实现的:还是拿之前的例子来说,先将值为

1

的节点放入队列,然后将先左孩子

4

放入队列,再将右孩子

2

放入队列,由于队列是先进先出型结构,所以保证了值为

4

的节点要先于值为

2

的孩子处理;同样地,第三层节点放入队列的顺序依次为

7, 20, 5

,与之后的处理顺序相同,保证了从左向右的顺序。过程如下图所示:(黄色代表加入队列的节点、粉色代表处理完成的节点、蓝色表示等待加入队列的节点)

1

2

3

4

5

6

7

一般地,在遍历完第

k

层的最后一个节点后,该层所有节点都被弹出了队列,且其孩子节点(均处于

k + 1

层)都被存入了队列且未处理,所以当前队列的长度就是

k + 1

层的节点数量。

所以,通过提前记录队列长度,可以方便地应对一些需要对各层进行特殊处理的问题。

特别地,为了防止二叉树为空、遍历到叶节点等情况,需要加入一些特判元素。修改后的模板如下:

// 1.初始化
queue<TreeNode*> q;
if(root == NULL) { // 二叉树为空
    return;
}
q.push(root);

// 2.遍历整棵树
while(1) {
    int cnt = q.size(); // 要处理层的节点个数
    if(cnt == 0) break; // 已经遍历完二叉树

    // 3.遍历该层
    while(cnt--) {
        TreeNode* cur = q.front();
        q.pop();

        // 4.对 cur 的操作,根据题意更改
        action(cur);

        // 5.将左右孩子放入队列
        if(cur->left) q.push(cur->left);
        if(cur->right) q.push(cur->right);
    }
}

2.几道例题

说明:对于不同的题目,只需要在我们的模板基础上增加或更改一些元素,所以对于下面的每道例题,我们在代码中只重点注释修改的部分。

第一题:二叉树的层序遍历

我们先从基础的力扣102题来入手:

题目要求返回一个二维容器,其中的每一个容器记录着某一层的所有节点值。我们只需要层序遍历二叉树,并按层遍历节点,将其加入

vector

。在遍历完该层后,将记录了该层所有节点的

vector

加入结果容器即可,代码如下:

vector<vector<int>> levelOrder(TreeNode* root) {
    // 声明结果二维容器
    vector<vector<int>> result;
    queue<TreeNode*> q;
    if(root == NULL) return result;
    q.push(root);
    while(1) {
        int cnt = q.size();
        if(cnt == 0) break;
        // 记录该层节点的容器
        vector<int> v;
        while(cnt--) {
            TreeNode* cur = q.front();
            q.pop();
            // 将当前节点存入容器
            v.push_back(cur->val);
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
        // 处理完该层,加入结果容器
        result.push_back(v);
    }
    return result;
}

第二题:二叉树的层序遍历 II

与上一道题不同,要求从下到上遍历。实际上我们只需要从上向下遍历后,将结果容器翻转即可。C++的标准库STL给我们提供了容器翻转的函数:

reverse(result.begin(), result.end())

第三题:二叉树的锯齿形层序遍历

与前两题不同,对于给定的如图所示的树,锯齿形遍历需要偶数层从右向左返回结果,奇数层从左向右返回结果,也即返回的结果序列应为:

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

本质上,我们只需要翻转偶数层的容器,就可以把从左向右的遍历转化为从右向左的遍历。在代码实现时,我们增加一个布尔型变量,记录当前层是否需要翻转,并每层将该变量取反即可:

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    // 当前层是否需要翻转
    bool flag = false;
    queue<TreeNode*> q;
    if(root == NULL) return result;
    q.push(root);
    while(1) {
        int cnt = q.size();
        if(cnt == 0) break;
        vector<int> v;
        while(cnt--) {
            TreeNode* cur = q.front();
            q.pop();
            v.push_back(cur->val);
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
        // 判断是否翻转
        if(flag) reverse(v.begin(), v.end());
        result.push_back(v);
        // 取反
        flag = !flag;
    }
    return result;
}

第四题:二叉树的最大深度

这是力扣第104题,看下题目:

在我们的模板里,每处理完一层,才退出内层循环,并开始新一轮外层循环。而本题要找最大深度,就是找一共处理了多少层,所以提前维护一个记录层数的变量

depth

,然后在外层循环内每次增加该变量即可:

int maxDepth(TreeNode* root) {
    int depth = 0; // 声明深度
    queue<TreeNode*> q;
    if(root == NULL) return 0;
    q.push(root);
    while(1) {
        int cnt = q.size();
        if(cnt == 0) break;
        depth++; // 处理新一层前深度自加
        while(cnt--) {
            TreeNode* cur = q.front();
            q.pop();
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
    }
    return depth;
}

特别地,

depth++

语句必须要放在判断

cnt = 0

的语句之后,否则若遍历到最后一层,深度自加之后才会退出循环,导致结果错误。

第五题:二叉树的最小深度

第111题要求“最小深度”(找到离根节点最近的叶子节点),由于我们进行的是层序遍历,只要找到一个叶子节点,该节点就一定是所求的最近节点。所以,遍历过程中增加判断叶子节点的部分即可。来看看代码:

int minDepth(TreeNode* root) {
    int depth = 0;
    queue<TreeNode*> q;
    if(root == NULL) return 0;
    q.push(root);
    while(1) {
        int cnt = q.size();
        if(cnt == 0) break;
        depth++;
        while(cnt--) {
            TreeNode* cur = q.front();
            q.pop();
            // 叶子节点
            if(!cur->left && !cur->right) return depth;
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
    }
    return depth;
}

最后总结

层序遍历的关键,要明确每一轮循环的具体过程。二叉树遍历相关的算法题,都是基于层序遍历框架的,我们只要搞清楚

root

节点本身要做什么,根据题目要求进行处理,再把左右孩子往队列里一放就行了。

如果本文讲的层序遍历对你有一些启发,请三连支持作者~~~

本文分享自微信公众号 - 程序员养成日记(programmer_grow)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-01-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • mysql索引原理,看这篇就够啦

    网上已经有了很多相关mysql索引原理的文章,但是都存在一些问题,有的是直接复制别人的比较老的文章,有的直接开篇讲B+Tree的原理,过程不是很清楚,即使原理讲...

    程序员养成日记
  • https详解

    HTTP是属于应用层的协议,它是基于TCP/IP的,所以它只是规定一些要传输的内容,以及头部信息,然后通过TCP协议进行传输,依靠IP协议进行寻址,通过一幅最简...

    程序员养成日记
  • mysql一张表到底能存多少数据?

    程序员平时和mysql打交道一定不少,可以说每天都有接触到,但是mysql一张表到底能存多少数据呢?计算根据是什么呢?接下来咱们逐一探讨

    程序员养成日记
  • HashMap实现多层级关系映射

    让我们先看第一层 map,即可将父 - 子节点的映射关系建立,如果没有父节点的设为 root 为父.,即为顶级节点.

    JavaEdge
  • 关于DOM的理解

    当创建了一个网页并把它加载到web浏览器中时,DOM就悄然而生。浏览器根据网页文档创建一个文档对象。

    Tz一号
  • (七):C++分布式实时应用框架 2.0

    版权声明:本文版权及所用技术归属smartguys团队所有,对于抄袭,非经同意转载等行为保留法律追究的权利!

    smartguys
  • 实践真知:一则因内存导致的集群故障

    故障概述 某天晚上,我方收到行方请求协助分析某数据库两节点RAC数据库问题,问题描述如下: 该 数据库版本为11.2.0.3,该版本中ASM内存管理机制有所变化...

    数据和云
  • VRTK插件总是报:Failed to load IVRRenderModels interface version的问题解决

    1.Assertion failed on expression: 'IsMatrixValid(matrix)' && Unity SteamVR: Fai...

    LittleU
  • 【腾讯云的1001种玩法】在腾讯云创建您的 SQL Server : HA 机准备篇

    目前 CLB 产品是基于应用层面的负载均衡,所以要实现业务感知并自动切换 IP 还得使用弹性网卡这一个特性来进行支持。

    李斯达
  • 【猫狗数据集】可视化resnet18的输出

    链接:https://pan.baidu.com/s/1l1AnBgkAAEhh0vI5_loWKw 提取码:2xq4

    西西嘛呦

扫码关注云+社区

领取腾讯云代金券

,,