直接通过输入判断是否为完全二叉树出现的问题

Question

在学习二叉树时刷到了该题：

链接：https://www.luogu.com.cn/problem/U264918

常规思路是按照宽度优先搜索一层一层去做，但我在想能不能通过输入的数据直接进行判断，于是我写了下方的代码：

#include<bits/stdc++.h>
using namespace std;

bool isComplete(int n){
    int count = 0,a,b; 
    while(n--){
        cin >> a >> b;
        if(a < 0 && b >= 0){//只有右子树没有左子树 
            return false; 
        }
        if(a >= 0 && b < 0){
            count++;
            if(count <= 1){
                continue; //尚未找到或只找到一个【有左子树但无右子树的节点】 
            }
            else{
                return false; //找到两个【有左子树但无右子树的节点】 
            }
        }
        if(count){ //如果已经找到【有左子树但无有字数的节点】 
            if(a >= 0 || b >= 0){ //后续节点不是叶子节点 
                return false;
            }
            continue;                
        }    
    }
    return true;
}

int main(){
    int n,m;
    cin >> n >> m;
    if(n <= 0){
        cout << "YES" << endl; //空树是完全二叉树 
    }
    else{
        cout << (isComplete(n) ? "YES" : "NO") << endl;
    }
    return 0;
}

但最终有一个测试案例没有通过，始终没想明白逻辑漏洞在哪里，各大AI也没有解释的很清楚。

希望能在这里得到解答，感谢各位！

Answer 1

感谢您提出了这个好问题！对一个问题良好的界定，已经将问题解决一半了！让【精通代码大仙】来帮您解答，本回答来自人工整理，并深度整合参考了付费大模型GPT4、Claude 3.5 Sonnet，以及最新的推理模型DeepSeek R1（DeepSeek-V3：AI 省钱与高效的奇迹，打破技术壁垒的东方魔法，Deepseek为什么会这么爆火？，DeepSeek大模型技术解析：从架构到应用的全面探索）的参考答案，如果还有疑问可以点击头像关注私信或评论(如果小黑屋了，无法评论，请私信)。 如果答案让您满意，请采纳、关注，您的采纳与关注是我最大的动力！非常感谢！

你的代码尝试通过直接分析输入数据来判断是否为完全二叉树，这个思路很有意思，但确实存在一些逻辑上的漏洞，导致无法通过所有测试用例。下面我将结合图片和题目描述，详细分析你的代码，指出问题所在，并提供一个更正后的思路。

问题分析

输入顺序的依赖性： 你的代码依赖于输入数据的顺序。完全二叉树的定义是，除了最后一层外，其他层都是满的，并且最后一层的所有节点都集中在左边。你的代码通过 cin >> a >> b 逐个读取左右子节点，并根据 a 和 b 的正负性来判断节点类型。但这种方法无法保证按照树的层次顺序（宽度优先）来读取节点。如果输入顺序不是按照层次顺序，你的判断逻辑就会出错。

根节点的缺失： 题目描述中提到，第一行的 n 和 m 分别表示树的大小和根节点。你的代码只使用了 n，而忽略了 m。这意味着你的代码无法判断输入的节点是否构成一棵有效的二叉树，更无法判断是否为完全二叉树。例如，输入的节点可能是不连通的，或者存在环，这些情况你的代码都无法处理。

count 变量的含义不明确： count 变量用于记录“有左子树但无右子树的节点”的数量。但这个变量的逻辑有些复杂，容易出错。例如，如果一个节点既没有左子树也没有右子树（叶子节点），你的代码会跳过这个节点，而不会更新 count。这可能会导致 count 的值不准确。

叶子节点的判断不完整： 你的代码只在 count > 0 的情况下才判断后续节点是否为叶子节点。这意味着，如果树的结构是完全平衡的（没有“有左子树但无右子树的节点”），你的代码就不会进行叶子节点的判断。这可能会导致误判。

更正后的思路

为了解决上述问题，我们需要一个更可靠的方法来判断是否为完全二叉树。以下是一个基于宽度优先搜索的思路，并结合输入数据进行优化：

构建树的结构： 首先，根据输入数据构建树的结构。可以使用一个 vector<pair<int, int>> 来存储每个节点的左右子节点。例如，tree[i].first 表示节点 i 的左子节点，tree[i].second 表示节点 i 的右子节点。如果子节点不存在，则设置为 -1。

宽度优先搜索： 从根节点开始，进行宽度优先搜索。使用一个队列来存储待访问的节点。

判断完全性： 在宽度优先搜索的过程中，记录以下信息：

has_null: 一个布尔变量，表示是否已经遇到过空节点（即没有左右子节点的节点）。
如果遇到一个节点，其左右子节点至少有一个为空，则将 has_null 设置为 true。
如果 has_null 已经为 true，并且后续又遇到了一个非叶子节点（即左右子节点都不为空），则说明该树不是完全二叉树。

代码示例

c++
复制代码
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool isComplete(int n, int root, vector<pair<int, int>>& tree) {
    queue<int> q;
    q.push(root);
    bool has_null = false;

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        int left = tree[node].first;
        int right = tree[node].second;

        if (left == -1 || right == -1) {
            has_null = true;
        }

        if (has_null && (left != -1 || right != -1)) {
            return false;
        }

        if (left != -1) {
            q.push(left);
        }
        if (right != -1) {
            q.push(right);
        }
    }

    return true;
}

int main() {
    int n, root;
    cin >> n >> root;

    vector<pair<int, int>> tree(n + 1); // 从 1 开始索引
    for (int i = 1; i <= n; ++i) {
        int a, b;
        cin >> a >> b;
        tree[i].first = a;
        tree[i].second = b;
    }

    if (n == 0) {
        cout << "YES" << endl;
    } else {
        cout << (isComplete(n, root, tree) ? "YES" : "NO") << endl;
    }

    return 0;
}


代码解释

isComplete(n, root, tree) 函数：

n: 树的大小。
root: 根节点。
tree: 存储树结构的 vector。
使用宽度优先搜索遍历树。
has_null: 标记是否遇到空节点。
如果 has_null 为 true 且后续节点不是叶子节点，则返回 false。

main() 函数：

读取输入数据，构建树的结构。
调用 isComplete() 函数判断是否为完全二叉树。
输出结果。

总结

你的原始思路很有创意，但由于对完全二叉树的理解不够深入，以及对输入顺序的依赖性，导致代码无法通过所有测试用例。更正后的思路基于宽度优先搜索，并结合输入数据构建树的结构，从而更准确地判断是否为完全二叉树。

希望这个详细的分析和代码示例能够帮助你理解问题所在，并成功解决这个问题。