二叉树oj -----＞判断二叉树是否为完全二叉树

小咪咪 2023-10-02 15:33 17阅读 0赞

**题目内容：**  
![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16][]

**解题思路：**

>  *  **判断是否为完全二叉树的最重要的一点就是知道什么是完全二叉树，或者什么不是完全二叉树，比较简单的是前者**
>  *  **完全二叉树的简单理解：****最后一层的前面的每一层结点都是满的，并且最后一层不满时，没有满的双亲结点的孩子结点必须靠左**
>  *  **我们借助于层序遍历（层序遍历时是不空才入队列，这次就让空也入队列）**
>  *  **判断时，当结点为空，就是我们判断的时候**
> 
> 1.  **如果cur为空且队列不为空，那么一定不是完全二叉树**
> 2.  **如果cur为空且队列也为空，那么一定是完全二叉树**

**解题代码：**

class Solution {
        public boolean isCompleteTree(TreeNode root) {
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);
            while(!q.isEmpty()){
                //每一层的结点的个数
                int count = q.size();
                for(int i = 0;i < count;i++){
                    //循环遍历每一个结点
                    TreeNode cur = q.poll();
                    //如果cur是空结点时，我们需要进行判断
                    //1.如果cur为空且队列不为空，那么一定不是完全二叉树
                    //2.如果cur为空且队列也为空，那么一定是完全二叉树
                    if(cur == null){
                        while(!q.isEmpty()){
                            if(q.poll() != null){
                                return false;
                            }
                        }
                        return true;
                    }
                    q.offer(cur.left);
                    q.offer(cur.right);
                }
            }
            return true;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/c7ac7c2670a948e3b9f29dc0300be36b.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16