987: 输出用先序遍历创建的二叉树是否为完全二叉树的判定结果

完全二叉树的定义是：除了最后一层外，每一层都必须填满，最后一层可以不填满，但是节点必须从左到右依次填入。因此，判断一个二叉树是否为完全二叉树，需要满足以下条件：

1. 如果一个节点只有右子树，那么这棵树一定不是完全二叉树。

2. 如果一个节点只有左子树或者没有子树，那么这个节点之后的所有节点都必须是叶子节点。

3. 如果一个节点既有左子树又有右子树，那么这个节点之后的所有节点都必须是叶子节点。

因此，我们可以通过先序遍历创建二叉树，并按照上述条件进行判断，来确定这棵二叉树是否为完全二叉树。

相关问题

判定二叉树是否为完全二叉树伪代码

确定一个二叉树是否为完全二叉树，可以通过递归遍历的方式进行检查。这里是一个简单的伪代码实现：

function isCompleteBinaryTree(root):
    if root is null:
        return true   // 空树视为完全二叉树

    // 检查当前节点是否有右孩子，并且左孩子的高度是否等于右孩子的高度加一
    if root.right is not null and height(root.left) != height(root.right) + 1:
        return false

    // 递归检查左子树和右子树
    if isCompleteBinaryTree(root.left) == false or isCompleteBinaryTree(root.right) == false:
        return false

    return true

function height(node):
    if node is null:
        return 0
    else:
        return 1 + max(height(node.left), height(node.right))

这个伪代码首先检查根节点是否存在右孩子并且左子树的高度是否比右子树高1；然后对左右子树分别进行递归判断。如果整个过程中所有子树都满足完全二叉树的条件，则返回`true`，否则返回`false`。

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

以下是判断二叉树是否为完全二叉树的 Python 代码：

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

def is_complete_tree(root: TreeNode) -> bool:
    if not root:
        return True
    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

该算法使用 BFS（广度优先搜索）遍历二叉树，当遍历到第一个没有左子树或右子树的节点时，将 flag 标记为 True，表示后面的节点都应该没有子树。如果后面的节点还有子树，则说明该二叉树不是完全二叉树。