非递归判断完全二叉树

可以使用层序遍历的方式进行判断。具体步骤如下：

1. 从根节点开始，将其入队。
2. 当队列不为空时，取出队首元素，判断其左右子节点是否存在。
3. 如果左右子节点都存在，则将左右子节点入队。
4. 如果左子节点不存在但右子节点存在，则该树不是完全二叉树。
5. 如果左子节点存在但右子节点不存在，或者左右子节点都不存在，则后面的所有节点必须都是叶子节点，否则该树不是完全二叉树。

如果遍历完整棵树都没有发现不符合条件的情况，则该树是完全二叉树。

相关问题

devc++判断是否为完全二叉树或非完全二叉树。

在Dev-C++中，判断一个二叉树是否为完全二叉树通常涉及到遍历和深度优先搜索（DFS）。完全二叉树的特点是除了最后一层外，每一层的节点都尽可能地填满，且最后一层的所有节点都在左边。

以下是一个简单的步骤来判断一个二叉树是否为完全二叉树：

1. **深度优先遍历**（DFS）：从根节点开始，对每个节点进行深度优先搜索，同时记录当前层的节点数以及最大层数。

2. **检查**：对于每一层，如果该层的节点数不是2的幂次减一，或者最后一层存在未满的右侧子节点，那么就不是完全二叉树。

3. **递归**：在遍历过程中，对每个子节点进行同样的判断，直到所有节点都被访问。

如果你想要实现这个算法，你可以创建一个递归函数，同时维护一个层数列表和一个节点计数器。例如，你可以使用前序遍历（根-左-右）来跟踪节点。

以下是代码示例的大致结构：

bool isCompleteBinaryTree(TreeNode* root) {
    if (root == nullptr) return true; // 空树视为完全二叉树

    int level = 1;
    vector<int> nodeCount(level, 0);
    dfs(root, level, nodeCount);

    for (int count : nodeCount) {
        if (count > (1 << level) - 1 || (level != nodeCount.size() && nodeCount.back() < (1 << (level - 1)))) {
            return false;
        }
    }

    return true;
}

void dfs(TreeNode* node, int level, vector<int>& nodeCount) {
    if (node == nullptr) return;

    nodeCount[level]++;
    dfs(node->left, level + 1, nodeCount);
    dfs(node->right, level + 1, nodeCount);
}

设二叉树采用二叉链表存储，设计非递归算法判断根结点为T的二叉树是否为完全二叉树。

可以使用层次遍历的方式来判断二叉树是否为完全二叉树。

具体过程如下：

1. 如果二叉树为空，则返回false。

2. 定义一个标记flag，初始值为false。

3. 对根结点进行层次遍历，如果遍历到某个结点的左右子树都不为空，且flag为true，则返回false；如果遍历到某个结点的左子树为空，或者左右子树都为空，则将flag设置为true；如果遍历到某个结点的左子树不为空，右子树为空，则将flag设置为true，并继续遍历。

4. 如果遍历完整个二叉树，都没有返回false，则说明该二叉树是完全二叉树，返回true。

代码实现如下：

def isCompleteTree(root):
    if not root:
        return False
    flag = False
    queue = [root]
    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

其中，queue用于存储当前层的结点，flag用于标记是否出现了左子树为空或左右子树都为空的情况。如果出现，则后面的结点必须满足左右子树都为空，否则就不是完全二叉树。