LintCode 69. Binary Tree Level Order Traversal 原创Java参考解答

LintCode 69. Binary Tree Level Order Traversal 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/binary-tree-level-order-traversal/

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

Example

Given binary tree {3,9,20,#,#,15,7},

return its level order traversal as:

解题思路

题目求做二叉树的层序遍历。

二叉树层序遍历是广度优先搜索BFS的最常见应用。

  1. 异常检查root节点是否为空
  2. 设一个装每一层node的queue队列,首先把root节点放入队列中。
  3. 把队列中node一层一层放入动态数组level中。并通过node.left 和 node.right把下一层的nodes放入queue中,以便下一次循环继续进行。把level结果加入result中。

算法的复杂度是就节点的数量,O(N),空间复杂度是一层的节点数,也是O(N)。

参考代码

相关题目

LintCode All in One 原创题目讲解汇总

发表评论

电子邮件地址不会被公开。 必填项已用*标注