判断二叉树是否为完全二叉树的代码
时间: 2023-09-23 18:06:44 浏览: 111
### 回答1:
可以使用递归算法来判断二叉树是否为完全二叉树,代码如下:def isCompleteTree(root):
if root is None:
return True
if root.left is None and root.right is None:
return True
if root.left is None:
return False
if root.right is None:
return isCompleteTree(root.left)
return isCompleteTree(root.left) and isCompleteTree(root.right)
### 回答2:
判断一棵二叉树是否为完全二叉树,可以使用层次遍历的方式进行判断。具体的代码如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isCompleteTree(root):
if not root:
return False
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
```
该方法使用了一个队列来进行层次遍历,每次从队列中取出一个节点,判断它的左右孩子节点是否为空。如果出现了某个节点的左孩子为空而右孩子不为空的情况,返回False;如果之前已经出现了空节点,但当前节点的左右孩子节点不为空,也返回False。只有当遍历完所有节点后都满足上述条件,才返回True,即为一棵完全二叉树。
### 回答3:
判断二叉树是否为完全二叉树可以采用层序遍历的方法来进行。首先从根节点开始遍历二叉树,将每一个遍历到的节点加入到一个队列中。在遍历的过程中,如果遇到空节点,则将其也加入到队列中,并且停止继续遍历。
接下来,从队列的头部开始出队列,判断出队的节点是否为一个临时的空节点。如果是,则继续出队其他节点直到遇到一个非空节点。如果在出队的过程中遇到了非空节点,那么该二叉树就不是完全二叉树。
继续遍历队列中的其他节点。如果队列中有其他非空节点,那么该二叉树就不是完全二叉树。
最后,如果队列中的所有元素都已经遍历完,而没有出现非空节点,则该二叉树是完全二叉树。
下面是用代码实现上述过程的方法:
```python
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isCompleteTree(root):
if root is None:
return True
queue = [root]
flag = False
while len(queue) > 0:
node = queue.pop(0)
if node is None:
flag = True
elif flag:
return False
else:
queue.append(node.left)
queue.append(node.right)
return True
```
其中,TreeNode是二叉树节点的定义,isCompleteTree函数用于判断二叉树是否为完全二叉树。