如何判定一个树是不是完全二叉树

判断一个树是否为完全二叉树，可以通过以下几个步骤：

1. 完全二叉树定义：完全二叉树是一种每个节点最多只有两个子节点，并且除了最后一层外，每一层的节点都尽可能地填满，从左到右顺序排列。

2. 检查叶子节点：首先，检查所有叶子节点（没有子节点的节点）是否都在最右边。如果树不是空的，并且存在最后一个非空节点，那么它必须是叶节点并且在最后一层的最左边。

3. 遍历：从根节点开始，递归地遍历每个节点。对于每个节点，如果它的右子节点存在且不为空，那么它的左子节点也必须存在。如果遇到某个节点的右子节点为空，但左子节点不为空，那么这个节点之前的部分就不可能是完全二叉树。

4. 层次检查：检查每个层次，除了最后一层，每个非叶子节点都应该有两个子节点。如果某个节点只有一个子节点，那么上一层可能就不完整。

5. 最后一层：如果树的最后一层不完全填满，但是所有的节点都是从左到右依次排列的，那么这棵树就是完全二叉树。

6. 返回结果：如果以上条件都满足，那么这棵树就是完全二叉树；如果不满足，就不是。

相关问题

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

以下是判断二叉树是否为完全二叉树的 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，表示后面的节点都应该没有子树。如果后面的节点还有子树，则说明该二叉树不是完全二叉树。

判定一颗完全二叉树java

判断一颗二叉树是否为完全二叉树，可以通过层次遍历的方式进行判断。以下是判定一颗完全二叉树的Java代码示例：

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class CompleteBinaryTreeChecker {
    public static boolean isCompleteBinaryTree(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean isEnd = false;

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            // 如果遇到空节点，则后面的节点都应该是空节点
            if (node == null) {
                isEnd = true;
            } else {
                // 如果前面已经遇到过空节点，说明不是完全二叉树
                if (isEnd) {
                    return false;
                }

                queue.offer(node.left);
                queue.offer(node.right);
            }
        }

        return true;
    }

    public static void main(String[] args) {
        // 构造一颗完全二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);

        boolean isComplete = isCompleteBinaryTree(root);
        System.out.println("Is the binary tree complete? " + isComplete);
    }
}