二叉树的完全性检验 图解题解

这道题到底在问什么

输入

[1,2,3,4,5,6]

输出

true(最后一层从左填满)

输入

[1,2,3,4,5,null,7]

输出

false(空位后又冒出 7)

最优解：一步一步想明白

1. 3记住「空孩子也入队;见空之后再遇真节点就 false」,下面逐帧套它。
2. 4根入队先看这棵树。把根 50 放进队列,见空开关 seen 还是关着。开始一个个出队。
3. 5seen 仍关出队真节点 50,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
4. 6空孩子也入队左孩子 30 入队;右孩子 80 入队。50 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
5. 7seen 仍关出队真节点 30,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
6. 8空孩子也入队左孩子 20 入队;右孩子 40 入队。30 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
7. 9seen 仍关出队真节点 80,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
8. 10空孩子也入队左孩子 60 入队;右孩子是空的,入队一个空位。80 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
9. 11seen 仍关出队真节点 20,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
10. 12空孩子也入队左孩子是空的,入队一个空位;右孩子是空的,入队一个空位。20 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
11. 13seen 仍关出队真节点 40,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
12. 14空孩子也入队左孩子是空的,入队一个空位;右孩子是空的,入队一个空位。40 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
13. 15seen 仍关出队真节点 60,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
14. 16空孩子也入队左孩子是空的,入队一个空位;右孩子是空的,入队一个空位。60 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
15. 17seen 打开出队出到一个空位,打开见空开关 seen。再看队列里剩下的:全是空位、没有任何真节点了。空位后面没再冒出节点,完全性成立。
16. 18true树 A(完全) 的结论:true(完全)。从左到右紧凑、最后一层靠左、没有空洞。
17. 19根入队先看这棵树。把根 50 放进队列,见空开关 seen 还是关着。开始一个个出队。
18. 20seen 仍关出队真节点 50,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
19. 21空孩子也入队左孩子 30 入队;右孩子 80 入队。50 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
20. 22seen 仍关出队真节点 30,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
21. 23空孩子也入队左孩子 20 入队;右孩子 40 入队。30 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
22. 24seen 仍关出队真节点 80,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
23. 25空孩子也入队左孩子是空的,入队一个空位;右孩子 70 入队。80 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
24. 26seen 仍关出队真节点 20,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
25. 27空孩子也入队左孩子是空的,入队一个空位;右孩子是空的,入队一个空位。20 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
26. 28seen 仍关出队真节点 40,此刻 seen 还关着,合法。接下来把它的左、右孩子都入队,空孩子也要入队一个空位。
27. 29空孩子也入队左孩子是空的,入队一个空位;右孩子是空的,入队一个空位。40 处理完(标绿)。把空孩子也排进队,是为了让可能的「空洞」在后面暴露出来。
28. 30seen 打开出队出到一个空位,打开见空开关 seen。注意队列后面还排着真节点,接下来只要再出到它,就违例了。
29. 31判定 false见空开关已经打开,却又出队到真节点 70(标红)。这说明前面的空位后面还有节点、中间留了空洞,判 false,不是完全二叉树。
30. 32false树 B(不完全) 的结论:false(不完全)。空位之后还冒出了节点,出现空洞,所以不完全。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
from collections import deque
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: 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

#include <algorithm>
#include <climits>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution { public: bool isCompleteTree(TreeNode* root){ queue<TreeNode*> q; q.push(root); bool seen=false; while(!q.empty()){ auto n=q.front(); q.pop(); if(!n) seen=true; else { if(seen) return false; q.push(n->left); q.push(n->right);} } return true; } };

import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}
class Solution { public boolean isCompleteTree(TreeNode root){ Queue<TreeNode> q=new LinkedList<>(); q.offer(root); boolean seen=false; while(!q.isEmpty()){ TreeNode n=q.poll(); if(n==null) seen=true; else { if(seen)return false; q.offer(n.left); q.offer(n.right); } } return true; } }

复杂度

面试官可能追问