给定一棵二叉树，判断它是否为完全二叉树。

Question

给定一个二叉树，编写一个函数来检查给定的二叉树是否为完全二叉树。

完全二叉树是一棵二叉树，除了最后一层外，每个层都是完全填充的，并且所有节点尽可能地靠左。来源：wikipedia 我的方法是使用队列进行BFS并计算节点数。运行循环直到队列不为空，但一旦发现以下条件之一成立，就会中断：

1. 节点不存在左子节点 2. 节点存在左子节点但不存在右子节点

现在，我们可以比较从上述方法得到的计数和树中原始节点的计数。如果两者相等，则为完全二叉树，否则不是。

请告诉我这种方法是否正确。谢谢。

这个问题与this相同。但我想在这里验证我的方法。

编辑： 下面@Boris Strandjev验证了该算法。在众多可用的算法中，我觉得这是最容易实现的算法。如果您不同意我的说法，请接受我的真诚道歉。

- Trying

---

@RahulTripathi 谢谢你提供的链接。但我想在这里验证我的算法。你能帮我吗？ - Trying

你是如何/何时计算节点的？ - Karoly Horvath

你甚至不需要计算节点数，只需查看是否到达了树的末尾或提前终止。计数与算法本身一样是O(n)，但似乎并不是必要的。 - vgru

请注意，您必须计算推入队列的节点数量，并在将节点的子节点推入队列后检查这些条件。 - mrmowji

Answer 1

你的算法应该能够解决这个问题。

你正在使用 BFS 的方式完全等同于绘制树形图，然后用手指从上到下、从左到右追踪节点。第一次无法继续时，停止用手指追踪。如果没有计算所有节点，那么显然结构与预期不符。

- Boris Strandjev

---

谢谢您的回复，但是我的代码对此会返回正确结果。假设队列为q。现在输入数据后，q 将具有数值1，然后弹出1并推入左节点2和右节点3。现在弹出2，2将没有左节点，因此停止。从这里我们得到计数3，但原始树有5个节点，因此这颗二叉树不完整。如果我错了，请纠正我。 - Trying

@trying：抱歉我误解了您的算法，我正在重新开始迭代，并将在2-3分钟内反馈。 - Boris Strandjev

@Trying已经编辑过了。我认为你可以采用这种方法。 - Boris Strandjev

你是说我的算法现在可以直接使用了吗？请确认一下。无论如何，感谢你的努力。 - Trying

@Trying 我确认。你的算法将按原样工作。我已在我的回答中解释了原因。 - Boris Strandjev