二叉树的完全性检验
难度:
标签:
题目描述
给你一棵二叉树的根节点 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
代码结果
运行时间: 19 ms, 内存: 16.1 MB
// 使用Java Stream的方式实现完全二叉树的判断
// 思路：同样使用广度优先搜索，并利用Java Stream处理节点的队列
import java.util.*;
import java.util.stream.*;
public class Solution {
public boolean isCompleteTree(TreeNode root) {
if (root == null) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean end = false;
while (!queue.isEmpty()) {
List<TreeNode> level = queue.stream().collect(Collectors.toList());
queue.clear();
for (TreeNode node : level) {
if (node == null) {
end = true;
} else {
if (end) return false;
queue.offer(node.left);
queue.offer(node.right);
}
}
}
return true;
}
}
// TreeNode类的定义：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}解释
方法:
该题解使用广度优先搜索的方式遍历二叉树。它使用一个双端队列来保存每一层的节点。在遍历过程中，如果当前节点的左右子节点都存在，则将其加入到下一层的队列中。如果遇到一个节点只有左子节点或者没有子节点，则将标记置为True，表示后续节点都必须是叶子节点。如果后续遇到非叶子节点，则说明该二叉树不是完全二叉树。在遍历的同时记录下最大深度和第一次遇到叶子节点时的深度，最后根据这两个深度判断是否为完全二叉树。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在广度优先搜索中，如何确保所有层除最后一层外都被完全填满？
▷🦆
当发现一个节点只有右子节点而没有左子节点时直接返回False，是基于什么完全二叉树的性质？
▷🦆
为什么在发现第一个叶子节点后，还需要继续检查后续节点是否为叶子节点？
▷🦆
您提到使用双端队列（deque），为什么选择双端队列而不是普通队列？
▷