java树的最大深度，使用队列

Question

在Narasimha Karumachi的《数据结构和算法变得简单》一书中， 这是找到树的最大深度的代码

出于某种原因，他向队列提供了一个null。我不明白为什么。删除它会破坏代码

我想知道作者为什么要添加一个null，以及用这种方式解决问题是否合适，因为我们可以在不添加null的情况下解决相同的问题

源代码：

public class MaxDepthInBinaryTreeWithLevelOrder {
// Returns the depth of this binary tree. The depth of a binary tree is the
// length of the longest path from this node to a leaf. The depth of a
// binary tree with no descendants (that is, just a leaf) is zero.
public int maxDepthLevelOrder(BinaryTreeNode root){
    if(root == null)
        return 0;
    int maxDepth = 1;
    Queue<BinaryTreeNode> q = new LinkedList<BinaryTreeNode>();
    q.offer(root);
    q.offer(null);   //  <----------- 'NULL' added Here
    while(!q.isEmpty()){
        BinaryTreeNode tmp = q.poll();
        if(tmp != null){
            if(tmp.getLeft() != null)
                q.offer(tmp.getLeft());
            if(tmp.right != null)
                q.offer(tmp.right);
        }else{
            if(!q.isEmpty()){
                ++maxDepth;
                q.offer(null); //  <--------- Here
            }
        }
    }
    return maxDepth;
 }
}

Answer 1

当队列以呼吸优先的方式遍历二进制搜索时，即覆盖所有处于相同深度级别的元素，然后移动到下一个深度级别

null在所有元素（以相同深度存在）添加到队列后添加到队列

从队列中删除null表明我们已经成功地遍历了相同深度级别的所有元素，这就是为什么我们增加了maxDepth计数器

null可以被看作是一个标志，让算法知道，是的，我们已经覆盖了所有元素，这些元素在相同的深度级别上存在