Python 检查二叉树是否完整的程序
假设我们有一棵二叉树;我们必须检查这是否是一棵完全二叉树。众所周知,在完全二叉树中,除了最后一层之外,所有层都填充了节点,并且最后一层中的所有节点都尽可能靠左。
因此,如果输入如下所示:
则输出将为 True
为了解决这个问题,我们将遵循以下步骤:
q := 一个双端队列
将根节点插入 q 的末尾
flag := False
当 q 不为空时,执行以下操作:
temp := 从 q 的左侧删除的元素
如果 temp 为空,则
flag := True
否则,当 flag 设置且 temp 不为空时,则
返回 False
否则,
将 temp 的左子节点插入 q 的末尾
将 temp 的右子节点插入 q 的末尾
返回 True
让我们看看下面的实现,以便更好地理解:
示例
from collections import deque class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right class Solution: def solve(self, root): q = deque() q.append(root) flag = False while q: temp = q.popleft() if not temp: flag = True elif flag and temp: return False else: q.append(temp.left) q.append(temp.right) return True ob = Solution() root = TreeNode(9) root.left = TreeNode(7) root.right = TreeNode(10) root.left.left = TreeNode(6) root.left.right = TreeNode(8) print(ob.solve(root))
输入
root = TreeNode(9) root.left = TreeNode(7) root.right = TreeNode(10) root.left.left = TreeNode(6) root.left.right = TreeNode(8)
Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.
输出
True
广告