二叉树的完全性检验
# 📃 题目描述
题目链接:958. 二叉树的完全性检验 (opens new window)
# 🔔 解题思路
层次遍历二叉树的每一层,遇到空结点之后再遇到不为空结点的结点,说明不为完全二叉树,说明不为完全二叉树,反之则为完全二叉树
和层次遍历模板有所不同的细节:
- null 节点也要入队,所以不要加 cur.left(cur.right) != null 的判断
class Solution {
public boolean isCompleteTree(TreeNode root) {
if (root == null || (root.left == null && root.right == null)) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
// 遇到空结点之后再遇到不为空结点的结点,说明不为完全二叉树
if (cur == null && !queue.isEmpty() && queue.peek() != null) {
return false;
}
if (cur != null) {
// null 也要入队,所以不要加 cur.left != null 的判断
queue.offer(cur.left);
queue.offer(cur.right);
}
}
return true;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10