小编典典

查找特定级别的二叉树中的所有节点(采访查询)

algorithm

我的意思是在特定级别上,而不是在特定级别上。有人可以检查我修改后的BFS算法吗?(其中大部分取自维基百科)

Queue levelorder(root, levelRequested){
      int currentLevel = 0;
      q = empty queue
      q.enqueue(root)
      while not q.empty do{
           if(currentLevel==levelRequested)
                 return q;
           node := q.dequeue()
           visit(node)
           if(node.left!=null || node.right!=null){
                 currentLevel++;
                 if node.left ≠ null
                       q.enqueue(node.left)
                 if node.right ≠ null
                       q.enqueue(node.right)
           }
      }
}

阅读 284

收藏
2020-07-28

共1个答案

小编典典

我认为递归解决方案会更加简洁:

/*
 * node - node being visited
 * clevel - current level
 * rlevel - requested level
 * result - result queue
 */
drill (node, clevel, rlevel, result) {
  if (clevel == rlevel) {
    result.enqueue (node);
  else {
    if (node.left != null)
      drill (node.left, clevel + 1, rlevel, result);
    if (node.right != null)
      drill (node.right, clevel + 1, rlevel, result);
  }
}

初始调用如下所示: drill (root, 0, n, rqueue);

2020-07-28