判断二叉树是否为完全二叉树算法代码
时间: 2023-10-19 09:10:15 浏览: 44
好的,下面是用 Python 语言实现的判断二叉树是否为完全二叉树的算法代码:
```
class Node:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_complete_tree(root):
if not root:
return True
queue = [root]
flag = False
while queue:
node = queue.pop(0)
if node.left:
if flag:
return False
queue.append(node.left)
else:
flag = True
if node.right:
if flag:
return False
queue.append(node.right)
else:
flag = True
return True
```
这个算法基于 BFS(宽度优先搜索)遍历二叉树的思想,判断每个节点是否合法。这里的关键在于如何判断某个节点是否合法,即是否满足完全二叉树的条件。具体来说,在遍历每个节点的时候,如果该节点有左子树或右子树,而且在前面的遍历中有某个节点没有左子树或右子树,则该节点不合法,不满足完全二叉树的条件。
希望这个算法能够解决您的问题。如果您还有其他问题,欢迎继续询问!