星星博客 »  > 

判断一棵二叉树是否完全二叉树

目录

    • 什么是完全二叉树
    • 思路
    • 代码

什么是完全二叉树

百度百科中对完全二叉树的定义如下:

若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。(注:第 h 层可能包含 1~ 2 h 2^h 2h 个节点。)

思路

使用队列层次遍历二叉树(dfs),当发现有空的结点后,之后还有非空结点,那么这就不是完全二叉树

例如:
在这里插入图片描述
入队的循序是:1 2 3 4 5 null 7
那么就发现null后面还有一个非空的结点,那么这个就不是完全二叉树

又比如:
在这里插入图片描述
入队的循序是:1 2 3 4 5 6
没有出现“发现有空的结点后,之后还有非空结点”的情况,这就是完全二叉树

代码

bool isCompleteTree(TreeNode* root) {
       	//判断是否为空树
        if(root==nullptr)
            return true;
        else{
            queue<TreeNode*> q;
            q.push(root);	//放入根结点
			
			//利用dfs层次遍历二叉树
            while(!q.empty()){
            	//空结点
                if(q.front()==NULL)
                    pre=true;	//设置pre为true
                
                //非空结点
                else{
                	//如果前面有空结点,这时又出现结点
                    if(pre)
                        return false;	//不是完全二叉树
                    
                    q.push(q.front()->left);	//队头的左孩子入队
                    q.push(q.front()->right); 	//队头的右孩子入队
                    
                } 

				//队头出队
                q.pop();  
            }
        }

		//是完全二叉树
        return true;
    }

相关文章