题目
给你一个二叉树的根节点 root ，判断其是否是一个有效的完全二叉树。
有效 完全二叉树定义如下：
有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 i（1≤i≤n）的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
解题思路：层次遍历
判断一棵树是否为「完全二叉树」，对其进行层次遍历，若遇到一个空结点，则其后面的结点必须全为空结点，否则不是完全二叉树。
复杂度分析
时间复杂度：
，
为二叉树的节点个数。
- 二叉树的每个节点最多被访问一次，因此时间复杂度为 
空间复杂度：
，
为二叉树的节点个数。
- 具有  个结点的完全二叉树的最大深度为 ，深度为  的完全二叉树至多有  个结点
- 队列最多存储  个节点，因此需要额外的  的空间。
我的代码
public boolean isAllTreeBST(TreeNode root){
if(root==null)return true;
LinkedList<TreeNode> q=new LinkedList<>();
q.addLast(root);
//当左右子树中出现一个空缺,说明后面不能再有结点
while(q.peek()!=null){
TreeNode node=q.poll();
q.addLast(node.left);
q.addLast(node.right);
}
//注意有可能队列里一堆 null 结点,需要判断是否全是空结点
while (!q.isEmpty()&&q.peek()==null)
q.poll();
return q.isEmpty();
}
若有收获，就点个赞吧
0 人点赞
