【面试题23】从上往下打印二叉树

【题目描述】

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

【解决方案】

利用队列实现。

我的代码实现，仅供参考：

 1         public static void PrintTopToBottom(BinaryTreeNode node)
 2         {
 3             if (node == null)
 4                 return;
 5 
 6             Queue<BinaryTreeNode> queue = new Queue<BinaryTreeNode>();
 7             queue.Enqueue(node);
 8 
 9             while (queue.Count > 0)
10             {
11                 node = queue.Dequeue();
12 
13                 Console.WriteLine(node.Value);
14 
15                 if (node.Left != null)
16                     queue.Enqueue(node.Left);
17 
18                 if (node.Right != null)
19                     queue.Enqueue(node.Right);
20             }
21         }

【本题扩展】

如果广度优先遍历一个有向图？这同样也可以基于队列实现。树是图的一种特殊退化形式，从上到下按层遍历二叉树，从本质上来说就是广度优先遍历二叉树。

【举一反三】

不管是广度优先遍历一个有向图还是一棵树，都要用到队列。