【LeetCode】从上到下打印二叉树 Java 题解
题目描述
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
复制代码
思路分析
这个题目题意简洁明了,借助树这种数据结构,考察树和队列的相关知识。
根据题意,我采用了 BFS 的方法解决这个问题。对于没有使用过 BFS 的同学,简要介绍一下 BFS 算法。
BFS 全称是 Breadth First Search,中文名是宽度优先搜索,也叫广度优先搜索。所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了,再访问下一层。
BFS 算法找到的路径是从起点开始的 最短 合法路径。这个很重要,在各位同学看到找最短路径的题目时候,脑海里可以考虑一下 BFS 算法。
通过代码
复制代码
上述代码,使用队列的时候,要注意队列的大小。每次都出队了一个元素,queue.size() 是动态获取队列的大小,为了保障我们把当前层的所有元素都取出,需要定义 size 变量,确定当前层的大小,获取当前层的所有元素。
总结
BFS 解法的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/3dca1069ef9a06e29f6c73882】。文章转载请联系作者。
评论