二叉树广度优先遍历( Depth First Search),这个算法是逐层遍历的,是从上到下,从左到右依次遍历,知道全部节点都被遍历完为止。
由于需要记录每一层的节点,所以需要记录其对应的父节点的子节点,同时具有顺序性,为此需要使用队列来装遍历所得的节点。
正常如果使用队列将上述入队就是成立 [1,2,3,4,5,6,7,8,9]
但是在队列中我们无非看出每一层有多少个。该怎么操作呢
因为每次入队应该是
次数 |
入队元素 |
出队元素 |
第一次 |
1 |
|
第二次 |
2,3 |
1 |
所以下一层一定是基于上一层遍历后得出的结果
即为每次出队是应该都是同一层的元素,并将同一层遍历后的子节点加入回队列中,为此可以采用每次遍历前先去计算队列中的元。
方法:在每一层进入以后遍历前,提前计算队列中存在元素个数再进行遍历
void bfs (TreeNode root){
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while(!queue.isEmpty()){
int n = queue.size(); // 记录每一层的个数
for(int i = 0; i < n ; i++){
TreeNode node = queue.poll();
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
}
}
}