二叉树 - 根据级别打印元素

Question

我在接受采访时问过这个问题:

假设我们上面有二叉树,我怎么能产生如下的输出

2 7 5 2 6 9 5 11 4

我回答可能是我们可以有一个级别计数变量,并通过检查每个节点的级别计数变量按顺序打印所有元素.可能我错了.

任何人都可以说明我们如何实现这一目标？

Answer 1

你需要对树进行宽度优先遍历. 这里描述如下:

广度优先遍历:深度优先不是通过树元素的唯一方法.另一种方法是逐级完成它们.

例如,每个元素都存在于树中的某个级别(或深度):

    tree
      ----
       j         <-- level 0
     /   \
    f      k     <-- level 1
  /   \      \
 a     h      z  <-- level 2
  \
   d             <-- level 3

人们喜欢以0开头编号.)

因此,如果我们想逐级访问元素(并且像往常一样从左到右),我们将从0开始使用j,然后转到第1级获取f和k,然后转到第2级对于a,h和z,最后到d级为3.

这种逐级遍历称为广度优先遍历,因为我们在深入之前探索给定级别的树的宽度,即树的全宽度.