完全二叉树的判断代码

以下是判断完全二叉树的代码实现：

bool isCompleteTree(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    bool end = false;
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node == nullptr) {
            end = true;
        } else {
            if (end) {
                return false;
            }
            q.push(node->left);
            q.push(node->right);
        }
    }
    return true;
}

该算法使用了层序遍历的思想，将每一层的节点按顺序加入队列中，如果在遍历过程中出现了空节点，那么后面的节点必须全部为空节点才能保证是完全二叉树，否则就不是完全二叉树。

相关问题

完全二叉树判断的伪代码

完全二叉树判断的伪代码如下：

1. 定义一个队列，用于存储待检查的节点。
2. 将根节点入队。
3. 循环执行以下步骤，直到队列为空：
1. 出队一个节点，并检查其左右子节点是否存在。
- 如果左子节点不存在但右子节点存在，返回 false。
- 如果左子节点存在但右子节点不存在，或者上一层已经出现了左右子节点不全的情况，后续的节点必须都是叶子节点，否则返回 false。
2. 如果左子节点存在，则将其入队。
3. 如果右子节点存在，则将其入队。
4. 如果队列为空，且所有节点都满足上述条件，则返回 true，表示是完全二叉树；否则返回 false。

伪代码实现：

function isCompleteBinaryTree(root):
    queue = new Queue()
    queue.enqueue(root)
    leafNodeFound = false
    
    while queue is not empty:
        node = queue.dequeue()
        
        if node.left is not null:
            if leafNodeFound or node.right is null:
                return false
            queue.enqueue(node.left)
            
        if node.right is not null:
            if leafNodeFound:
                return false
            queue.enqueue(node.right)
        else:
            leafNodeFound = true
    
    return true

注意：上述伪代码假设已经定义了一个队列数据结构，并实现了相应的 enqueue 和 dequeue 操作。

判断二叉树是否为完全二叉树的代码

### 回答1：

可以使用递归算法来判断二叉树是否为完全二叉树，代码如下：def isCompleteTree(root):
if root is None:
return True

if root.left is None and root.right is None:
return True

if root.left is None:
return False

if root.right is None:
return isCompleteTree(root.left)

return isCompleteTree(root.left) and isCompleteTree(root.right)

### 回答2：
判断一棵二叉树是否为完全二叉树，可以使用层次遍历的方式进行判断。具体的代码如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isCompleteTree(root):
    if not root:
        return False
    
    queue = [root]
    flag = False  # 标识是否出现空节点
    
    while queue:
        node = queue.pop(0)
        
        if node.left:
            # 如果之前出现了空节点，则此时不能再出现左孩子节点为空的情况
            if flag:
                return False
            queue.append(node.left)
        else:
            flag = True
        
        if node.right:
            # 如果之前出现了空节点，则此时不能再出现右孩子节点为空的情况
            if flag:
                return False
            queue.append(node.right)
        else:
            flag = True
    
    return True

该方法使用了一个队列来进行层次遍历，每次从队列中取出一个节点，判断它的左右孩子节点是否为空。如果出现了某个节点的左孩子为空而右孩子不为空的情况，返回False；如果之前已经出现了空节点，但当前节点的左右孩子节点不为空，也返回False。只有当遍历完所有节点后都满足上述条件，才返回True，即为一棵完全二叉树。

### 回答3：
判断二叉树是否为完全二叉树可以采用层序遍历的方法来进行。首先从根节点开始遍历二叉树，将每一个遍历到的节点加入到一个队列中。在遍历的过程中，如果遇到空节点，则将其也加入到队列中，并且停止继续遍历。

接下来，从队列的头部开始出队列，判断出队的节点是否为一个临时的空节点。如果是，则继续出队其他节点直到遇到一个非空节点。如果在出队的过程中遇到了非空节点，那么该二叉树就不是完全二叉树。

继续遍历队列中的其他节点。如果队列中有其他非空节点，那么该二叉树就不是完全二叉树。

最后，如果队列中的所有元素都已经遍历完，而没有出现非空节点，则该二叉树是完全二叉树。

下面是用代码实现上述过程的方法：

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isCompleteTree(root):
    if root is None:
        return True

    queue = [root]
    flag = False

    while len(queue) > 0:
        node = queue.pop(0)

        if node is None:
            flag = True
        elif flag:
            return False
        else:
            queue.append(node.left)
            queue.append(node.right)

    return True

其中，TreeNode是二叉树节点的定义，isCompleteTree函数用于判断二叉树是否为完全二叉树。