动画：面试必刷之从上到下打印二叉树

题目
从上到下打印出二叉树的每个节点，同一层的节点按照顺序从左往右的顺序打印。例如：输入下图中的二叉树，则依次打印8,6,10,5,7,9,11。

如图：

问题分析

对于二叉树的遍历，我们所熟悉的有前序遍历、中序遍历和后续遍历，而对于这种一层层的遍历，我们叫做按层遍历。

我们先从根节点开始，比如我们输出了根节点，要想输出下一层（也就是根节点）的子节点，必须在输出根节点的值前，我们需要记录根节点的两个子节点，为了在下一轮进行输出做准备。

同样的道理，我们再输出第三层节点的时候，必须在遍历第二层节点前，记录第三层有哪些节点，这样才能进行下一轮的输出。

其实我们上边所说的保存节点的过程我们可以用到数组保存。但是有没有发现一个问题，比如说我们保存了第二层节点，再保存第三层节点的时候，那么这个数组里的第二层节点会被遍历两遍。你可能会说，直接在遍历第三层的时候，我们只清空数组再保存节点不行吗。

如果按照这个逻辑的话，你会发现我们需要两个数组来保存，一个用来遍历当前层，另一个用来保存当前层的下一节点。但是我们有个巧妙的方法来用一个数组解决此问题。就是队列，如下图动画。

动画实现

解题思路

首先判断输入的树是否为空。

1    if(root == null){2        return false;3    }

然后开始用一个 while 循环开始进行输出。在循环内在队列中取出一个节点，然后判断该节点的是否存在子节点，如果存在，我们继续入队。否则，下一步输出当前节点的值。

 1    const queue = []; 2    const result = []; 3    queue.push(root); 4 5    while(queue.length !== 0){ 6        // 出队 7        let currentNode = queue.shift(); 8 9        // 存储下结点值10        if(currentNode.left !== null){11            queue.push(currentNode.left);12        }13        if(currentNode.rigth !== null){14            queue.push(currentNode.rigth);15        }1617        // 同时输出当前结点值18        result.push(currentNode.val);19    }

代码实现

JavaScript

Java

Python

测试用例

完全二叉树、非完全二叉树 —— 普通测试
只有左、右子节点的二叉树、只有一个节点的二叉树 —— 特殊测试
空树 —— 输入测试

更多相关文章

随机推荐