LeetCode 题解工作台
二叉树的完全性检验
给你一棵二叉树的根节点 root ，请你判断这棵树是否是一棵 完全二叉树 。 在一棵 完全二叉树 中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都尽可能靠左。最后一层（第 h 层）中可以包含 1 到 2 h 个节点。 示例 1： 输入： root = [1,2,3,4,5,6] 输…
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
class Solution: def isCompleteTree(self, root: TreeNode) -> bool:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵二叉树的根节点 root ，请你判断这棵树是否是一棵 完全二叉树 。
在一棵 完全二叉树 中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都尽可能靠左。最后一层（第 h 层）中可以包含 1 到 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，节点值为 {1} 和 {2,3} 的两层），且最后一层中的所有节点（{4,5,6}）尽可能靠左。
示例 2：
输入：root = [1,2,3,4,5,null,7] 输出：false 解释：值为 7 的节点不满足条件「节点尽可能靠左」。
提示：
- 树中节点数目在范围
[1, 100]内 1 <= Node.val <= 1000
解题思路
方法一
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isCompleteTree(self, root: TreeNode) -> bool:
q = deque([root])
while q:
node = q.popleft()
if node is None:
break
q.append(node.left)
q.append(node.right)
return all(node is None for node in q)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on the ability to traverse trees efficiently.
- question_mark
Ensure the candidate considers how to handle null nodes and left-to-right order.
- question_mark
Evaluate the candidate's awareness of space optimization techniques during traversal.
常见陷阱
外企场景- error
Failing to account for the placement of nodes after encountering null values.
- error
Misunderstanding the completeness condition for the last level.
- error
Not considering the space complexity and unnecessarily storing large amounts of data during traversal.
进阶变体
外企场景- arrow_right_alt
Modified versions where the tree can be non-binary.
- arrow_right_alt
Cases where the tree structure is less balanced, requiring different traversal strategies.
- arrow_right_alt
Variation with constraints on tree height, making certain optimization techniques more important.