使用队列的树的最大深度

在Narasimha Karumanchi所着的"数据结构和算法"一书中,这是用于找到树的最大深度的代码.

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 q = new LinkedList();
    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;
 }
}

prem kumar.. 5

null用于标记级别的结尾.

作者使用级别顺序遍历来查找树的深度.他使用Queue数据结构来实现它.为了划分彼此相邻的水平,null用作水平标记.

例如.他首先插入root,然后是null标记.在while循环第一次迭代中,队列中的第一个元素被删除,如果不是null,则将左右子元素添加到队列中.当删除下一个元素时,它将为null,表示级别1的结束.现在,如果队列不为空,则可能有许多其他级别.因此再次插入空标记.

注意: - 只要null从队列中删除元素,就意味着当前级别中没有更多元素,并且下一级别的所有子级都将添加到队列中,并且下一级别中不再有剩余元素.所以我们可以再次插入空标记来标记下一级的结束.

null用于标记级别的结尾.

作者使用级别顺序遍历来查找树的深度.他使用Queue数据结构来实现它.为了划分彼此相邻的水平,null用作水平标记.

例如.他首先插入root,然后是null标记.在while循环第一次迭代中,队列中的第一个元素被删除,如果不是null,则将左右子元素添加到队列中.当删除下一个元素时,它将为null,表示级别1的结束.现在,如果队列不为空,则可能有许多其他级别.因此再次插入空标记.

注意: - 只要null从队列中删除元素,就意味着当前级别中没有更多元素,并且下一级别的所有子级都将添加到队列中,并且下一级别中不再有剩余元素.所以我们可以再次插入空标记来标记下一级的结束.