从上到下打印二叉树(层序遍历)｜刷题打卡

柔情只为你懂 2022-11-06 08:55 120阅读 0赞

# 一、题目描述 #

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

**例如:**  
给定二叉树: \[3,9,20,null,null,15,7\],

3
       / \
      9  20
        /  \
       15   7

[3,9,20,15,7]

**提示：**

节点总数 <= 1000

# 二、思路分析 #

要从上到下，从左到右，一层一层的访问二叉树的节点。

![93af250f66ce77d1fa1c244e629bea46.png][]

遍历当前层的时候需要考虑下一层的遍历顺序，

先访问的节点，在下一层时也是需要先被访问，

可以利用队列**先进先出**的特性来存储下一层的节点，

遍历到B的时候需要把D、E记录下来；遍历到C的时候把F、G记录下来…

# 三、AC 代码 #

/**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {number[]}
     */
    var levelOrder = function(root) {
        if(!root) return []
        let res = [];
      const queue = [] // 初始化队列queue
        // 根结点首先入队
        queue.push(root)
        // 队列不为空，说明没有遍历完全
        while(queue.length) {
            const top =  queue.shift() // 取出队头元素  
            // 记录节点数据
            res.push(top.val)
            // 如果左子树存在，用队列记录左子树
            if(top.left) {
                queue.push(top.left)
            }
            // 如果右子树存在，用队列记录右子树
            if(top.right) {
                queue.push(top.right)
            }
        }
        return res;
    };

# 四、总结 #

*  利用队列**先进先出**的特性可以保证层序遍历的顺序。

[93af250f66ce77d1fa1c244e629bea46.png]: /images/20221023/fe883d813c614b56ace18c3f8e4960b8.png