如何进行分层遍历二叉树问题

共计 532 个字符，预计需要花费 2 分钟才能阅读完成。

如何进行分层遍历二叉树问题，针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

初阶：给一棵二叉树，按照层次进行输出，第一行输出第一层的节点，第二行输出第二层，如此类推。
进阶：如果只给你 O(h) 的额外空间该怎么办？（h 为树的高度） 

答：

初阶：采用宽度（广度）优先搜索算法 BFS。用一个队列存储一层的节点，通过一层节点扩展出下一层节点。实现的时候有两种方式：一种方式是队列中同时存储层数，发现层数不同了，就换行输出；另一种方式是记录每一层的头尾，多套一层循环输出每一层。时间复杂度 O(n)，空间复杂度 O(n)

进阶：采用迭代搜索。迭代搜索的意思是，设定一个层数限制 x，利用深度优先搜索的方式往下搜索，每次搜到 x 这一层就不再往下继续递归了。通过逐渐放宽 x 来实现每一层的搜索，也就是 x 从 1 到 h 进行枚举（h 为树的高度）。时间复杂度 O(nh)，空间复杂度 O(h)。迭代搜索是常用的在空间不足的情况下替代宽度优先搜索的方法。是一种用时间换取空间的方法。

关于如何进行分层遍历二叉树问题问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注丸趣 TV 行业资讯频道了解更多相关知识。