题目描述：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例1:

截屏2022-06-10 下午5.15.34.png

1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例2:

1
2
输入：root = [1]
输出：[[1]]

示例3:

1
2
输入：root = []
输出：[]

题解方法一： 广度优先搜索

解题思路：

  • 广度优先遍历是按层层推进的方式，遍历每一层的节点。题目要求的是返回每一层的节点值，所以这题用广度优先来做非常合适。

  • 广度优先需要用队列作为辅助结构，我们先将根节点放到队列中，然后不断遍历队列。
    截屏2022-06-10 下午5.36.13.png

  • 首先拿出根节点，如果左子树/右子树不为空，就将他们放入队列中。第一遍处理完后，根节点已经从队列中拿走了，而根节点的两个孩子已放入队列中了，现在队列中就有两个节点 2 和 5。

截屏2022-06-10 下午5.36.56.png

  • 第二次处理，会将 2 和 5 这两个节点从队列中拿走，然后再将 2 和 5 的子节点放入队列中，现在队列中就有三个节点 3，4，6。

截屏2022-06-10 下午5.37.23.png

  • 我们把每层遍历到的节点都放入到一个结果集中，最后返回这个结果集就可以了。
    代码实现如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    var levelOrder = function(root) {
        const ret = [];
        if (!root) {
            return ret;
        }

        const q = [];
        q.push(root);
        while (q.length !== 0) {
            const currentLevelSize = q.length;
            ret.push([]);
            for (let i = 1; i <= currentLevelSize; ++i) {
                const node = q.shift();
                ret[ret.length - 1].push(node.val);
                if (node.left) q.push(node.left);
                if (node.right) q.push(node.right);
            }
        }
            
        return ret;
    };

    总结：大功告成✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️

参考链接: