python设计算法判断一棵树是否为完全二叉树
时间: 2023-10-26 12:06:57 浏览: 63
要判断一棵树是否为完全二叉树,需要遍历一遍这棵树,并对每个节点进行判断。具体方法如下:
1. 从根节点开始,对树进行层次遍历(广度优先遍历);
2. 对于每个节点,如果该节点没有左子树但有右子树,则该树不是完全二叉树;如果该节点有左子树但没有右子树,或者左右子树都为空,则从此节点开始,后面遍历到的节点都必须是叶子节点,否则该树不是完全二叉树;
3. 如果遍历完成后仍未发现问题,则该树是完全二叉树。
下面是 Python 代码实现:
``` python
# 定义树的节点
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 判断一棵树是否为完全二叉树
def isCompleteTree(root: TreeNode) -> bool:
# 如果根节点为空,直接返回 True
if not root:
return True
queue = [root] # 存储遍历过的节点
leaf = False # 是否已经遇到过非叶子节点
while queue:
node = queue.pop(0)
# 如果当前节点是非叶子节点
if not node.left and node.right:
return False
# 如果当前节点已经遇到过非叶子节点
if leaf and (node.left or node.right):
return False
# 如果当前节点没有右子树
if not node.right:
leaf = True
# 将当前节点的左右子树加入队列
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# 遍历结束,没有发现问题,则为完全二叉树
return True
```