AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

[LeetCode算法]有了二叉树层序遍历，妈妈再也不用担心我不会做二叉树层级题了

2023-05-30 302
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 博主最近在刷`leetcode`，做到二叉树套题的时候发现很多题的解题思路都是基于二叉树的层序遍历来完成的，因此写下这篇文章，记录一下二叉树层序遍历这件"神器"在实战的运用。

您好，如果喜欢我的文章，可以关注我的公众号「量子前端」，将不定期关注推送前端好文~

前言

博主最近在刷leetcode，做到二叉树套题的时候发现很多题的解题思路都是基于二叉树的层序遍历来完成的，因此写下这篇文章，记录一下二叉树层序遍历这件"神器"在实战的运用。

[leetcode] 102.二叉树的层序遍历

leetcode题目链接

image.png

二叉树的层序遍历与传统的前序、中序、后序遍历都有一些区别，他是按层级、从左到右、从上到下进行遍历的，因此当我在遍历当前层节点的时候，肯定需要记录当前层所有节点的left、right，保存到队列中，进行下一轮遍历，直到节点没有left、right，则代表已经遍历到了最后一层了。

因此需要借助一个辅助数据结构——队列，队列先进后出，符合层序遍历的顺序性，其实此题就是队列 + 广度优先遍历 的一道结合题。

直接看代码吧：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
   
   
    const res = [], queue = [];
    queue.push(root);
    if(root === null) return res;

    while(queue.length !== 0) {
   
   
        let level = [];
        const length = queue.length
        for(var i = 0; i < length; i++) {
   
   
            var node = queue.shift();
            level.push(node.val);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        res.push(level);
    }
    return res;
};

接下来我们逐行分析代码。

  • 首先定义了一个结果和一个队列，对应res和queue，将顶层的root节点加入到队列中，开启循环。
  • 在每一轮while 循环中，我们从左到右依次取出节点(shift api)并且判断每个节点下一层是否有后代(left、right)的判断，如果有，则加入到队列中。
  • const length = queue.length记录了队列在每一层遍历开始时的最初状态，保证了后面的for循环遍历的内容是当前层的节点，不会因为left、right加入到队列中的节点影响到当前层的循环轮数。
  • 最终，队列中所有节点都遍历完毕，在for循环中也没有发现新的下层节点，循环结束，返回结果。

此时我们就掌握了二叉树的层序遍历了，那么如下九道力扣上的题目，只需要修改模板的两三行代码（不能再多了），便可打倒！你真的会发现，理解了层序遍历后，解决这些关联题，会如鱼得水一般简单

  • 102.二叉树的层序遍历
  • 107.二叉树的层次遍历II
  • 199.二叉树的右视图
  • 637.二叉树的层平均值
  • 429.N叉树的前序遍历
  • 515.在每个树行中找最大值
  • 116.填充每个节点的下一个右侧节点指针
  • 117.填充每个节点的下一个右侧节点指针II
  • 104.二叉树的最大深度
  • 111.二叉树的最小深度

[leetcode] 107.二叉树的层序遍历II

leetcode题目链接

image.png

此题与102.二叉树的层序遍历极其相似，只需要把最后的res结果的排列顺序改变一下即可，代码架构和102完全一样。

代码:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
   
   
    var res = [], queue = [];
    queue.push(root);
    if(root === null) return res;
    while(queue.length) {
   
   
        let length = queue.length;
        const level = [];
        for(var i = 0; i < length; i++) {
   
   
            var node = queue.shift();
            level.push(node.val)
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        res.unshift(level);
    }
    return res;
};

[leetcode] 199.二叉树的右视图

leetcode题目链接

image.png

此题从题目描述中可以看到，需要收集每一层的最后一个节点，有了"神器"的你，此时已经有思路了吧？这不是只需要在每一轮while循环中的for里加一个判断条件，取出最后一个节点就好了？上代码！

代码:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
   
   
    var res = [], queue = [];
    queue.push(root);
    if(root === null ) return res;
    while(queue.length !== 0 ){
   
   
        const length = queue.length;
        for(var i = 0; i < length; i++) {
   
   
            var node = queue.shift();
            if(i === length - 1) {
   
   
                res.push(node.val);
            }
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return res;
};

[leetcode] 637.二叉树的层平均值

leetcode题目链接

image.png

此题只需要在每层节点取完以后，对节点的平均值进行一个计算即可，相比于前面几题，区别在收集的返回结果不一样，解题代码架构没有区别。

代码:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var averageOfLevels = function(root) {
   
   
    var res = [], queue = [];
    queue.push(root);
    if(root === null) return res;

    while(queue.length !== 0) {
   
   
        const length = queue.length;
        let total = 0;
        for(var i = 0; i < length; i++) {
   
   
            let node = queue.shift();
            total += node.val;
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        res.push(total / length);
    }
    return res;
};

[leetcode] 429.N叉树的层序遍历

leetcode题目链接

image.png

此题会有一点小弯需要绕一下，首先数据结构不同，TreeNode节点是这样的：

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

也就是说我们在每一层节点的循环中，不是再去收集节点的left、right了，而是去遍历节点的children，将children中的节点加入到队列中。

代码:

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
   
   
    var res = [], queue = [];
    queue.push(root);
    if(root === null) return res;

    while(queue.length !== 0) {
   
   
        var level = [];
        var length = queue.length;
        for(var i = 0; i < length; i++) {
   
   
            var node = queue.shift();
            level.push(node.val)
            for(var item of node.children) {
   
   
                item && queue.push(item);
            }
        }
        res.push(level);
    }
    return res;
};

[leetcode] 515. 在每个树行中找最大值

leetcode题目链接

image.png

此题类似于637.二叉树的层平均值，只是每一层收集的内容变成了最大值。

代码:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var largestValues = function(root) {
   
   
    var res = [], queue = [];
    queue.push(root);
    if(root === null) return res;

    while(queue.length !== 0) {
   
   
        const length = queue.length;
        const list = [];
        for(var i = 0; i < length; i++) {
   
   
            var node = queue.shift();
            list.push(node.val);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        res.push(Math.max(...list));
    }
    return res;
};

[leetcode] 116. 填充每个节点的下一个右侧节点指针

leetcode题目链接

image.png

此题无需重新组装新的返回内容，只需要重新组建root中的每一个节点即可，每一个TreeNode默认的next为null，根据题目要求，在每一层所有节点，我们对除了最右节点以外的所有节点添加一个next属性即可，根据队列先进先出的原则，next的值就是queue[0]，也就是队列的首项。

代码:

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
   
   
    var queue = [root];
    if(root === null) return root;
    while(queue.length) {
   
   
        const length = queue.length;
        for(var i = 0; i < length; i++) {
   
   
            var node = queue.shift();
            if(i < length - 1) {
   
   
                node.next = queue[0];
            }
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return root;
};

[leetcode] 117. 填充每个节点的下一个右侧节点指针II

leetcode题目链接

image.png

此题与116. 填充每个节点的下一个右侧节点指针 类似，直接上代码。

代码:

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
   
   
   if (root === null) {
   
   
        return null;
    }
    let queue = [root];
    while (queue.length > 0) {
   
   
        let n = queue.length;
        for (let i=0; i<n; i++) {
   
   
            let node = queue.shift();
            if (i < n-1) node.next = queue[0];
            if (node.left != null) queue.push(node.left);
            if (node.right != null) queue.push(node.right);
        }
    }
    return root;
};

[leetcode] 104. 二叉树的最大深度

leetcode题目链接

image.png

此题比较简单，只需要在遍历的过程中不断记录height即可，当层序遍历结束，返回height就解决了。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
   
   
    if(root === null) return root;
    var queue = [root];
    var height = 0;
    while(queue.length > 0) {
   
   
        const length = queue.length;
        height++;
        for(var i = 0; i < length; i++) {
   
   
            var node = queue.shift();
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return height
};

[leetcode] 111. 二叉树的最小深度

leetcode题目链接

image.png

此题与104. 二叉树的最大深度类似，区别在于需要提前结束循环，通过判断树节点是否满足node.left === null && node.right === null，就可以知道二叉树的最小深度是哪个节点，将该节点遍历时的height返回即可。

代码:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
   
   
    if(root === null) return root;
    var queue = [root];
    var height = 0;

    while(queue.length > 0) {
   
   
        const n = queue.length;
        height++;
        for(var i = 0; i < n; i++) {
   
   
            var node = queue.shift();
            if(node.left === null && node.right === null ) {
   
   
                return height;
            }
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return height;
};

结尾

二叉树的层序遍历本质上是队列+广度优先遍历的结合运用诞生出来的"神器"，此时就会发现通过它可以解决leetcode中很多二叉树的题目！

如果本文对你有帮助，不妨点个赞吧~

文章标签：
前端开发
API
算法
关键词：
算法leetcode
LeetCode二叉树
LeetCode层序遍历
算法二叉树
LeetCode算法
sorryhc
目录
相关文章
aliyun4145988376
|
2月前
|
存储 人工智能 算法
从零掌握贪心算法Java版：LeetCode 10题实战解析（上）
在算法世界里，有一种思想如同生活中的"见好就收"——每次做出当前看来最优的选择，寄希望于通过局部最优达成全局最优。这种思想就是贪心算法，它以其简洁高效的特点，成为解决最优问题的利器。今天我们就来系统学习贪心算法的核心思想，并通过10道LeetCode经典题目实战演练，带你掌握这种"步步为营"的解题思维。
aliyun4145988376
302 0
飞川001
|
7月前
|
Go 开发者 索引
【LeetCode 热题100】路径与祖先：二叉树中的深度追踪技巧（力扣33 / 81/ 153/154）（Go语言版）
本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目，涵盖了无重复和有重复元素的情况。通过二分查找的变形应用，文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同，并推荐了类似题目，帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者，都能从中获得实用的解题技巧和代码实现方法。
飞川001
336 14
飞川001
|
8月前
|
算法 Go
【LeetCode 热题100】深入理解二叉树结构变化与路径特性（力扣104 / 226 / 114 / 543）（Go语言版）
本博客深入探讨二叉树的深度计算、结构变换与路径分析，涵盖四道经典题目：104（最大深度）、226（翻转二叉树）、114（展开为链表）和543（二叉树直径）。通过递归与遍历策略（前序、后序等），解析每题的核心思路与实现方法。结合代码示例（Go语言），帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题，欢迎持续关注！
飞川001
226 10
飞川001
|
8月前
|
存储 算法 数据可视化
【二叉树遍历入门：从中序遍历到层序与右视图】【LeetCode 热题100】94:二叉树的中序遍历、102:二叉树的层序遍历、199:二叉树的右视图（详细解析）（Go语言版）
本文详细解析了二叉树的三种经典遍历方式：中序遍历（94题）、层序遍历（102题）和右视图（199题）。通过递归与迭代实现中序遍历，深入理解深度优先搜索（DFS）；借助队列完成层序遍历和右视图，掌握广度优先搜索（BFS）。文章对比DFS与BFS的思维方式，总结不同遍历的应用场景，为后续构造树结构奠定基础。
飞川001
433 10
飞川001
|
8月前
|
Go
【LeetCode 热题100】路径与祖先：二叉树中的深度追踪技巧（力扣437 / 236 ）（Go语言版）
本文深入探讨二叉树中路径与祖先问题，涵盖两道经典题目：LeetCode 437（路径总和 III）和236（最近公共祖先）。对于路径总和 III，文章分析了双递归暴力解法与前缀和优化方法，后者通过哈希表记录路径和，将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中，采用后序遍历递归查找，利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点，帮助读者掌握深度追踪技巧，理解树结构中路径与节点关系的本质。这类问题在面试中高频出现，掌握其解法意义重大。
飞川001
221 4
飞川001
|
8月前
|
Go 索引 Perl
【LeetCode 热题100】【二叉树构造题精讲：前序 + 中序建树 & 有序数组构造 BST】（详细解析）（Go语言版）
本文详细解析了二叉树构造的两类经典问题：通过前序与中序遍历重建二叉树（LeetCode 105），以及将有序数组转化为平衡二叉搜索树（BST，LeetCode 108）。文章从核心思路、递归解法到实现细节逐一拆解，强调通过索引控制子树范围以优化性能，并对比两题的不同构造逻辑。最后总结通用构造套路，提供进阶思考方向，帮助彻底掌握二叉树构造类题目。
飞川001
505 9
修己xj
|
9月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构，广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型（如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等）及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历，并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力，优化算法设计。
修己xj
321 10
算法系列之数据结构-二叉树
光明顶阳顶天
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码，实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
光明顶阳顶天
351 64
RossyYan
|
11月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
RossyYan
551 3
小山那边
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代，文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用，并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构，每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树，能高效地管理和检索文件。相较于顺序查找，二叉树查找每次比较可排除一半子树，极大提升了查找效率，尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数，展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
小山那边
220 5

热门文章

最新文章

  • 1
    当“爆款书”遇上大数据：出版业的老路，正在被算法改写
  • 2
    LeetCode - 45. Jump Game II
  • 3
    [LeetCode] Compare Version Numbers 版本比较
  • 4
    【LeetCode从零单排】No.169 Majority Element(hashmap用法)
  • 5
    [LeetCode] Department Highest Salary 系里最高薪水
  • 6
    [LeetCode] Unique Word Abbreviation
  • 7
    leetcode 104 Maximum Depth of Binary Tree二叉树求深度
  • 8
    LeetCode - 36. Valid Sudoku
  • 9
    [LeetCode] Serialize and Deserialize Binary Tree
  • 10
    LeetCode：149_Max Points on a line | 寻找一条直线上最多点的数量 | Hard
  • 1
    当“爆款书”遇上大数据：出版业的老路，正在被算法改写
    183
  • 2
    当AI成为航天员的“大脑外设”：智能算法如何优化人类的长期太空旅行
    171
  • 3
    电脑监控管理中的 C# 哈希表进程资源索引算法
    194
  • 4
    HNSW算法实战：用分层图索引替换k-NN暴力搜索
    248
  • 5
    基于python智能推荐算法的全屋定制系统
    244
  • 6
    使用哈里斯角Harris和SIFT算法来实现局部特征匹配（Matlab代码实现）
    191
  • 7
    基于导向滤波的暗通道去雾算法在灰度与彩色图像可见度复原中的研究（Matlab代码实现）
    197
  • 8
    【水下图像增强融合算法】基于融合的水下图像与视频增强研究（Matlab代码实现）
    316
  • 9
    结合多种启发式解码方法的混合多目标进化算法，用于解决带工人约束的混合流水车间调度问题（Matlab代码实现）
    175
  • 10
    【基于TTNRBO优化DBN回归预测】基于瞬态三角牛顿-拉夫逊优化算法（TTNRBO）优化深度信念网络（DBN）数据回归预测研究（Matlab代码实现）
    167

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台
    • 下一篇
    基于Python+Vue开发的口腔牙科预约管理系统