这棵树

普通的bfs

1
2
3
4
5
6
7
8
9
 while(!queue.isEmpty())
 {     
    root=queue.poll();
    depth++;
    if(root.left!=null)
        queue.offer(root.left);
    if(root.right!=null)  
        queue.offer(root.right);   
}

求深度用的bfs

1
2
3
4
5
6
7
8
9
while (!queue.isEmpty()) {
           res++;
           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);
           }
       }

对应的每次while时队列状态如下图。

可以看到上面的第2 3步会对应两个while导致深度加了两次，而下面的2 3步合到一个for里，相当于每次while对应一层。

这题和429. N 叉树的层序遍历很像 都是bfs while里面套个for 这样一次while就是一层。