树的最大深度，使用队列

在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; 
} 
}

来源

2016-01-09 Charan

我不明白这个算法（也许如果我花了更多的时间，我可以弄清楚），但似乎他使用'null'作为某种标记。 – ajb

我认为这是一个广度优先搜索。该算法搜索树的宽度。一个'null'标记每个宽度的结束，所以当找到'null'时，深度计数器就会增加。 – markspace

null被用于标记一个电平的端部。

作者正在使用级别遍历来查找树的深度。他使用队列数据结构来实现它。划分彼此相邻的级别null用作级别标记。

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

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

来源

2016-01-09 07:38:08

由于队列以第一种方式穿过呼吸中的二进制搜索，即覆盖深度相同的所有元素，然后移动到下一级深度。

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

从队列中移除null表明我们已经成功遍历了存在于相同深度级别的所有元素，因此我们增加了maxDepth计数器。

null可以被看作是标志让算法知道是的，我们已经涵盖了所有存在于相同深度级别的元素。

来源

2016-01-09 14:33:35

树的最大深度，使用队列

回答

相关问题