判定完全二叉树 bfs
时间: 2023-12-11 13:34:01 浏览: 32
以下是判定完全二叉树BFS的方法:
1.首先,我们需要对树进行层序遍历,使用队列来实现。
2.在遍历过程中,我们需要记录每个节点的编号,编号规则如下:
- 对于任意节点node,它的编号为i,则其左子节点的编号为2i,右子节点的编号为2i+1。
- 对于任意节点node,它的编号为i,则其父节点的编号为i/2(向下取整)。
3.在遍历过程中,我们需要记录每一层的最左边和最右边的节点编号,以及最大宽度。
4.最后,我们判断最大宽度是否等于最后一层的节点数,如果相等,则该树为完全二叉树,否则不是。
以下是Python代码实现:
```python
from collections import deque
def isCompleteTree(root):
if not root:
return True
queue = deque([(root, 1)])
cur_level = 1
left, right = 1, 1
max_width = 0
while queue:
node, num = queue.popleft()
if node.left:
queue.append((node.left, num * 2))
if node.right:
queue.append((node.right, num * 2 + 1))
if num // 2 != cur_level:
cur_level = num // 2
left = num
right = num
max_width = max(max_width, right - left + 1)
return max_width == right - left + 1
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)