Leetcode 二叉树的层序遍历
问题定义:
给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
算法思路:
传统的层序遍历算法,while循环里每趟循环只取一个元素(队首)并访问,不合要求。但只需简单修改就可以使用。
我们维护两个列表: thisLevel, nextLevel, 分别存储当前层和下一层的树结点。
初始化时thisLevel只有一个元素:root(根节点);
在循环中遍历thisLevel的每个元素,如果它有非空子树,将它加入nextLevel中。
循环结束后,将当前层的所有元素以列表方式加入用来输出的列表(result)中。由于thisLevel中存储的是结点对象,需要转换成数值再存储,我们将thisLevel遍历一遍,将数结点的值存储在列表Value中。再将列表Value加入列表result。
此时进行更新:thisLevel = nextLevel,将当前层转换到下一层,继续循环直到当前层为空。
代码:
时间复杂度:O(n)