用Python判断一棵树是否为完全二叉树。
时间: 2024-03-24 17:37:14 浏览: 15
判断一棵树是否为完全二叉树,需要对树的结构进行深入分析,通常可以使用BFS(广度优先搜索)算法来实现。
具体来说,可以按照以下步骤进行判断:
1. 定义一个队列,将根节点入队。
2. 对队列进行循环遍历,直到队列为空:
- 弹出队列的首个节点,并判断该节点是否为最后一层的节点(即该节点的左右子节点为空)。
- 如果该节点不是最后一层的节点,则将其左右子节点依次入队。
- 如果该节点是最后一层的节点,则其后面的节点必须都为叶子节点,否则该树不是完全二叉树。
3. 如果队列遍历完毕,仍未发现不符合要求的节点,则该树为完全二叉树。
以下是用Python实现判断一棵树是否为完全二叉树的代码示例:
```python
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def is_complete_tree(root: TreeNode) -> bool:
if not root:
return True
queue = [root]
is_last_layer = False
while queue:
node = queue.pop(0)
if (not node.left and node.right) or (is_last_layer and (node.left or node.right)):
return False
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not node.left or not node.right:
is_last_layer = True
return True
```
需要注意的是,在判断节点是否为最后一层的节点时,需要同时判断其左右子节点是否为空。如果左右子节点只有一个为空,则该节点不是最后一层的节点。如果左右子节点都为空,则该节点一定是最后一层的节点。