树的最大深度，使用队列

Question

在 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<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 用于标记关卡结束。

作者正在使用层序遍历来求树的深度。他使用Queue数据结构来实现。为了划分彼此相邻的级别，null 用作级别标记。

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

注意：- 每当 null 元素被从队列中移除时，这意味着当前级别中没有更多元素，并且其下一级中的所有子元素都被添加到队列中，并且下一级中没有更多元素剩余.所以我们可以再次插入空标记来标记下一层的结束。

Answer 2

As Queue首先遍历Breath中的Binary search，即覆盖所有处于相同深度级别的元素，然后移动到下一个深度级别。

null 在所有元素（存在于同一深度级别）添加到队列后添加到队列。

从队列中移除 null 表明我们已成功遍历同一深度级别的所有元素，这就是我们增加 maxDepth 计数器的原因。

null 可以被视为标志，让算法知道是的，我们已经覆盖了相同深度级别的所有元素。

树的最大深度，使用队列

Maximum depth of a tree, using a queue

java

algorithm

tree

binary-tree

data-structures