250-判断二叉树是不是完全二叉树

超、凢脫俗 2022-11-14 10:25 209阅读 0赞

## 判断二叉树是不是完全二叉树 ##

**完全二叉树**：每一层均达到最大层，除最后一层外。最后一层从右向左依次缺省若干个节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
**解题思路：**  
我们用层次方式遍历。  
我们定义一个队列，入队列的时候，即便是空的指针，我们也把这个空指针入队列，出队列的时候，出了一个空，后续入进去的全部是空，则是完全二叉树！

**示例下图解析：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
我们首先把0入队列，0出来，入1和2，1出来，入的是3和4，2出来，入的是5和空，3出来，入的是7和8，4出来，入的是空和空，5出来，入的是空和空。遇到的第一个空，就退出来，如果接下去都是空，就是完全二叉树，如果出的时候有不为空的，就不是完全二叉树。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
**上图：空 不连续。不是完全二叉树**

bool Is_Comp(BtNode* ptr)
    {
        
    	bool res=true;
    	if(ptr==nullptr) return res;
    	std::queue<BtNode*> qu;
    	qu.push(ptr);
    	while(!qu.empty())
    	{
        
    		ptr=qu.front(); qu.pop();
    		if(ptr==nullptr) break;
    		qu.push(ptr->leftchild);
    		qu.push(ptr->rightchild);
    	}
    	while(!qu.empty())
    	{
        
    		ptr=qu.front(); qu.pop();
    		if(ptr!=nullptr)
    		{
        
    			res=false;
    			break;
    		}
    	}
    	return res;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/3712e058361a4be9bdf0386427b9756d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/166d0dff40a5421897c33abc5b34cb94.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/2021032821115176.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center