要求:从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
思路: 使用二叉树的广度遍历BFS。(广度(层次遍历)优先遍历用队列,深度优先遍历用栈)
广搜的套路就是用一个队列保存将要搜索的这一层的元素,然后逐个搜索;
1、将第一个元素加入队列
2、队列不为空时取队首元素
3、将下一层元素加入队尾
4、调到第二步,直到队列为空
public class L33_PrintFromTopToBottom {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode0 root){
ArrayList<Integer> list = new ArrayList<>();
Queue<TreeNode0> qu = new LinkedList<>();
if(root!=null){
qu.add(root);
}else{
return list;
}
while(!qu.isEmpty()){
TreeNode0 temp = qu.poll();
list.add(temp.value);
if(temp.left!=null){
qu.add(temp.left);
}
if(temp.right!=null){
qu.add(temp.right);
}
}
return list;
}
}
时间复杂度 O(N) : N 为二叉树的节点数量,即 BFS 需循环 N 次。
空间复杂度 O(N) : 最差情况下,即当树为平衡二叉树时,最多有 N/2 个树节点同时在 queue 中,使用 O(N) 大小的额外空间。
网友评论