LeetCode 102.二叉树的层次遍历 - JavaScript

心谭博客

发布于 2020-04-21 15:30:27

6270

发布于 2020-04-21 15:30:27

文章被收录于专栏：YuanXin

题目描述：给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

例如给定二叉树:

返回其层次遍历结果：

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

题目分析

从题目中可以看到，本题考察的是二叉树的层序遍历，并且在结果中要体现出“层次”。

思路

稍微改变一下对队列的使用，就可以在遍历过程中体现出层次，大致过程如下：

初始化 queue，用于存储当前层的节点
检查 queue 是否为空
- 如果不为空：依次遍历当前 queue 内的所有节点，检查每个节点的左右子节点，将不为空的子节点放入 queue，继续循环
- 如果为空：跳出循环

在上面的思路上，稍微改造下就可以了。代码如下：

// ac地址：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
// 原文地址：https://xxoo521.com/2020-02-20-level-travel/

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if (!root) return [];
    const queue = [root];
    const res = []; // 存放遍历结果
    let level = 0; // 代表当前层数
    while (queue.length) {
        res[level] = []; // 第level层的遍历结果

        let levelNum = queue.length; // 第level层的节点数量
        while (levelNum--) {
            const front = queue.shift();
            res[level].push(front.val);
            if (front.left) queue.push(front.left);
            if (front.right) queue.push(front.right);
        }

        level++;
    }
    return res;
};

时间复杂度是O(N)，空间复杂度是O(N)。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-02-20，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法