题目描述
思路解析动画文字版
记住「空孩子也入队;见空之后再遇真节点就 false」,下面逐帧套它。
树 A(完全):开始 BFS：先看这棵树。把根 50 放进队列,见空开关 seen 还是关着。开始一个个出队。
树 A(完全):出队 50：出队真节点 50,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
树 A(完全):50 的孩子入队：左孩子 30 入队;右孩子 80 入队。50 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
树 A(完全):出队 30：出队真节点 30,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
树 A(完全):30 的孩子入队：左孩子 20 入队;右孩子 40 入队。30 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
树 A(完全):出队 80：出队真节点 80,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
树 A(完全):80 的孩子入队：左孩子 60 入队;右孩子是空的,入队一个空位。80 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
树 A(完全):出队 20：出队真节点 20,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
树 A(完全):20 的孩子入队：左孩子是空的,入队一个空位;右孩子是空的,入队一个空位。20 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
树 A(完全):出队 40：出队真节点 40,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
树 A(完全):40 的孩子入队：左孩子是空的,入队一个空位;右孩子是空的,入队一个空位。40 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
树 A(完全):出队 60：出队真节点 60,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
树 A(完全):60 的孩子入队：左孩子是空的,入队一个空位;右孩子是空的,入队一个空位。60 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
树 A(完全):出到空位：出队出到一个空位,打开见空开关 seen。再看队列里剩下的:全是空位、没有任何真节点了。空位后面没再冒出节点,完全性成立。
树 A(完全):结论：树 A(完全) 的结论:true(完全)。从左到右紧凑、最后一层靠左、没有空洞。
树 B(不完全):开始 BFS：先看这棵树。把根 50 放进队列,见空开关 seen 还是关着。开始一个个出队。
树 B(不完全):出队 50：出队真节点 50,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
树 B(不完全):50 的孩子入队：左孩子 30 入队;右孩子 80 入队。50 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
树 B(不完全):出队 30：出队真节点 30,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
树 B(不完全):30 的孩子入队：左孩子 20 入队;右孩子 40 入队。30 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
树 B(不完全):出队 80：出队真节点 80,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
树 B(不完全):80 的孩子入队：左孩子是空的,入队一个空位;右孩子 70 入队。80 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
树 B(不完全):出队 20：出队真节点 20,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
树 B(不完全):20 的孩子入队：左孩子是空的,入队一个空位;右孩子是空的,入队一个空位。20 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
树 B(不完全):出队 40：出队真节点 40,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
树 B(不完全):40 的孩子入队：左孩子是空的,入队一个空位;右孩子是空的,入队一个空位。40 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
树 B(不完全):出到空位：出队出到一个空位,打开见空开关 seen。注意队列后面还排着真节点,接下来只要再出到它,就违例了。
树 B(不完全):违例：见空开关已经打开,却又出队到真节点 70(标红)。这说明前面的空位后面还有节点、中间留了空洞,判 false,不是完全二叉树。
树 B(不完全):结论：树 B(不完全) 的结论:false(不完全)。空位之后还冒出了节点,出现空洞,所以不完全。
边界:空树、单节点、满树都为 true;关键永远是「见空之后还有没有真节点」。
两个高频追问:可用下标编号 maxId==n 判;完全允许最后一层靠左留空。
参考代码
from typing import List, Optionalfrom collections import dequeclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def isCompleteTree(self, root: Optional[TreeNode]) -> bool: q = deque([root]) seen_null = False while q: node = q.popleft() if not node: seen_null = True else: if seen_null: return False q.append(node.left); q.append(node.right) return True复杂度
- 时间：O(n)，每个真节点入队、出队各一次,连同它们的空孩子占位也是常数倍,总共 O(n)
- 空间：O(w)，队列里最多同时装一层的节点(含空占位),w 是树的最大宽度,最坏可到 O(n)
易错点
面试追问把动画讲成自己的话
追问能不能用「按下标编号」的方法做?
追问为什么最后一层有空位也可能是完全的?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
从叶结点开始的最小字符串
LeetCode 988 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题