广东中山建设信息网站,开发网站广州,免费网站建站 网页,凡科建站官网入口#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ bfs 求解思路 实现代码 运行结果 共勉 题目链接
958. 二叉树的完全性检验
⛲ 题目描述
给你一棵二叉树的根节点 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 求解思路实现代码运行结果 ⚡ bfs 求解思路
题目要求判断一棵二叉树是否是完全二叉树。完全二叉树的定义是 除了最后一层外其他层的节点都是满的。最后一层的节点从左到右连续排列不能有空缺。 具体求解算法如下所示
层序遍历使用队列进行层序遍历逐层检查节点是否符合完全二叉树的性质。标记空节点 在遍历过程中如果遇到一个空节点则后续的所有节点都必须是空节点。如果遇到一个非空节点但其前面的节点是空节点则说明树不是完全二叉树。 终止条件遍历结束后如果没有发现违反完全二叉树性质的情况则返回 true。
有了基本的思路接下来我们就来通过代码来实现一下。 实现代码
/*** Definition for a binary tree node.* public 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) {if (root null)return true;QueueTreeNode queue new LinkedList();queue.add(root);TreeNode pre root;while (!queue.isEmpty()) {TreeNode node queue.poll();if (pre null node ! null) {return false;}if (node ! null) {queue.add(node.left);queue.add(node.right);}pre node;}return true;}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
