基于层次遍历判断是否为完全二叉树

package main

import . "nc_tools"

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return bool布尔型
 */
func isCompleteTree(root *TreeNode) bool {
	if root == nil {
		return true
	}
    
    notComplete := false
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        tempQueue := []*TreeNode{}
        for _, node := range queue {
            if node == nil {
                notComplete = true
                continue
            }
            if notComplete {
                return false // 第二次出现空节点
            }
            
            tempQueue = append(tempQueue, node.Left)
            tempQueue = append(tempQueue, node.Right)
        }
        queue = tempQueue
    }
    
    return true
}

public boolean isCompleteTree (TreeNode root) {
        // write code here
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode cur;
        boolean flag = false;
        while(!queue.isEmpty()){
            cur = queue.poll();
            if(cur == null){
                flag = true;
                continue;
            }
            if(flag) return false;
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        return true;
    }

class Solution {
  public:
    int y = 1e9;
    int cnt = 0;
    void dfs(TreeNode* root, int x) {
        if (!root) {
            y = min(y, x);
            return;
        }
        ++cnt;
        dfs(root->left, x * 2);
        dfs(root->right, x * 2 + 1);
    }
    bool isCompleteTree(TreeNode* root) {
        dfs(root, 1);
        return y == cnt + 1;
    }
};

bool isCompleteTree(struct TreeNode* root ) {
    struct TreeNode **queue=(struct TreeNode*)malloc(sizeof(struct TreeNode*)*100);
    int f=-1,r=-1;
    queue[++r]=root;
    int flag=0;
    while(r!=f){
        struct TreeNode *k=queue[++f];
        if(k!=NULL){
            if(flag) return 0;
            queue[++r]=k->left;
            queue[++r]=k->right;
        }
        else{
            flag=1;
        }        
    }
    return flag;
}

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        # write code here
        if root is None:
            return True
        
        queue = [root]
        is_missing_child = False
        
        while len(queue) > 0:
            node = queue.pop(0)
            
            # 针对缺失节点的情况进行判断
            if node is None:
                is_missing_child = True
                continue
            elif is_missing_child:
                return False
            
            # 将左右子节点加入队列
            queue.append(node.left)
            queue.append(node.right)
        
        return True

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
  bool isCompleteTree(TreeNode* root) {
  // 层序遍历 利用完全二叉树条件
    if (root == nullptr) return true;
    queue<TreeNode* > que;
    que.push(root);
    while (!que.empty()) {
      TreeNode* cur = que.front();
      que.pop();
      if (cur != nullptr) {
        // 完全二叉树条件1：有右无左 返回false
        if (cur -> left == nullptr && cur -> right != nullptr)
          return false;
        // cur的左右子节点入队
        que.push(cur -> left);
        que.push(cur -> right);
      } else 
        // 遇到空节点 循环终止
        break;
    }
    // 二次while判断不满足上述条件1（左无右有）后仍有不满足：
    // 条件2 完全二叉树叶子节点须从左至右依次排列
    // 队列还为空 如果头结点非空 则返回false 空则出队
    while (!que.empty()) {
      if (que.front() != nullptr) return false;
      else que.pop(); 
    }
    return true;
  }
};

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool isCompleteTree(TreeNode* root) {
        // write code here
        if(!root)return 1;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {//空指针也可以压入
            int sz = q.size();
            while(sz--) {
                auto cur = q.front();
                if(!cur){//域间空指针后看后没是不是全是空指针
                    while(!q.empty() && !q.front())
                        q.pop();
                    if(q.empty())return 1;//全是空
                    else return 0;//不全是空
                }
                q.pop();
                // 空指针也压进去
                q.push(cur->left);
                q.push(cur->right);

            }
            }
        return 1;
        
    }
};

public class Solution {
    int ans = 0;
    int helper(TreeNode root, int idx){
        if(root == null) return 0;
        ans = Math.max(ans, idx);
        return 1 + helper(root.left, idx * 2) + helper(root.right, idx * 2 + 1);
    }
    public boolean isCompleteTree (TreeNode root) {
        return helper(root, 1) == ans;
    }
}

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <queue>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    bool isCompleteTree(TreeNode* root) {
        if (root == nullptr)
            return true;
        queue<TreeNode*> s;
        vector<int> v;
        int size = 0;
        s.push(root); 
        while (!s.empty()) {
            TreeNode* now = s.front();
            s.pop();
            if(now!=nullptr){
                v.push_back(now->val);
                s.push(now->left);
                s.push(now->right);
            }
            else{
                v.push_back(-1);
            }
            size++;
        }
        bool flag =true;
        for(int i=size-1;i>0;i--){
            if(v[i]!=-1){
                flag=false;
            }
            if(v[i]==-1&&!flag)
            return false;
        }
        return true;
    }
};

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    bool isCompleteTree(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }

        queue<TreeNode*> queue;
        queue.push(root);
        bool hasNull = false;

        while (!queue.empty()) {
            TreeNode* node = queue.front();
            queue.pop();

            // 如果之前遇到过空节点，并且当前节点不为空，则该二叉树不是完全二叉树
            if (hasNull && node != nullptr) {
                return false;
            }

            // 如果当前节点为空，则标记遇到过空节点
            if (node == nullptr) {
                hasNull = true;
            } else {
                queue.push(node->left);
                queue.push(node->right);
            }
        }
        return true;
    }
};

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool isCompleteTree(TreeNode* root) {
        // 时间复杂度O(N)，空间复杂度O(N)
        if (root == nullptr) return true;
        queue<TreeNode*> que;
        que.push(root);
        bool flag = false;
        while (!que.empty()) {
            TreeNode* node = que.front();
            que.pop();
            if (node->left) {
                if (flag) return false;
                que.push(node->left);
            } else flag = true;
            if (node->right) {
                if (flag) return false;
                que.push(node->right);
            } else flag = true;
        }
        return true;
    }
};