从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。
例如: 给定二叉树: [3,9,20,null,null,15,7],
3 / 9 20 / 15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
提示:
节点总数 <= 1000
方法1:递推
依然是BFS,只是要多2个List去保存结果,还需要2个变量一个记录下一层的节点数目,另一个记录当前层没有打印的节点数目
用一个队列Queue保存节点,标准BFS遍历模版如下:
这个方法会把对应的引用数据清掉
,直接new ArrayList()即可方法2:递归
初始化一个k作为树层数标记,对于大的list而言,每一层都是一个小list,当这个小list没有时,新建这个小list添加进头结点(大list的长度<=k)
如果存在这一层的小list,就在这个小list中继续添加这一层的数据即res[depth].append(node.val)
之后进行头结点左子树和右子树的递归,每一次递归层数+1即
traversal(node.left, depth + 1)
traversal(node.right, depth + 1)
·/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null) return new ArrayList();
List<List<Integer>> result = new ArrayList<>();
List<Integer> row = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int rownode = 1;
int nextrow = 0;
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
row.add(temp.val);
if(temp.left!=null){
queue.add(temp.left);
nextrow++;
}
if(temp.right!=null){
queue.add(temp.right);
nextrow++;
}
rownode--;
if(rownode==0){
result.add(row);
rownode = nextrow;
nextrow = 0;
row = new ArrayList();
}
}
return result;
}
}
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
def traversal(node, depth):
if not node:
return
if len(res) <= depth: # 如果结果集没有对应层数的列表,则先创建并将当前节点值压入
temp = []
temp.append(node.val)
res.append(temp)
else: # 如果有,直接压入对应层数所对应的列表
res[depth].append(node.val)
traversal(node.left, depth + 1)
traversal(node.right, depth + 1)
traversal(root, 0)
return res