大家好，我是考100分的小小码 ，祝大家学习进步，加薪顺利呀。今天说一说判断一棵二叉树是否为完全二叉树的算法_完全二叉树怎么判别,希望您对编程的造诣更进一步.
小知识，大挑战！本文正在参与“程序员必备小知识”创作活动
判断一棵二叉树是否为完全二叉树
问题描述
给定一棵二叉树，请判断该二叉树是否为完全二叉树。
输出描述：输出是否为完全二叉树。
注意：空子树我们认为是符合完全二叉树。
示例：
输入：{2,1,3}
输出：true
分析问题
在引出完全二叉树的定义之前，我们先来看一下什么是满二叉树。满二叉树是指除了最后一层叶子节点外，每一层上的所有结点都有两个子结点二叉树。而完全二叉树是由满二叉树引出来的。对于深度为K的，有n个节点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时，我们称之为完全二叉树。如下图所示。
根据完全二叉树的定义，我们可以通过广度优先搜索进行求解，每遇到一个节点时，我们进行判断。
- 如果节点的左孩子为空且右孩子不为空的时，该树不是完全二叉树。
- 如果第一次发现左、右两个孩子不是双全的时候，我们记录一下。如果后面访问到的节点出现非叶子节点时，那么表明该树不是完全二叉树。
def isAllTreeBST(self, root):
#如果是空树，直接返回True，因为空树也是完全二叉树
if not root:
return True
queue=collections.deque([root])
#遇到第一个非双全的节点，打个标记
flag=False
while queue:
node = queue.popleft()
left = node.left
right = node.right
#如果flag为true 且 访问到的节点出现非叶子节点时，表明是非完全树，返回False
if flag and not (left==None and right==None):
return False
#左孩子为空且右孩子不为空的时,表明是非完全树，返回False
if left==None and right != None:
return False
if left!=None:
queue.append(left)
if right!=None:
queue.append(right)
#遇到非全节点，设置flag=True
if left==None or right==None:
flag = True
return True
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/13581.html
