P15801 [GESP202603 六级] 完全二叉树 题解

题目描述

给定一棵包含 n 个结点的有根二叉树，结点依次以 1,2,…,n 编号，根结点编号为 1。

对于结点 i，其左儿子的编号记为 li​，右儿子编号记为 ri​。特别地，如果左儿子不存在则 li​=0，如果右儿子不存在则 ri​=0。

树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 n 棵子树中，有多少棵子树是完全二叉树。

输入格式

第一行，一个正整数 n，表示有根二叉树结点数量。

接下来 n 行，每行两个正整数 li​,ri​，表示结点 i 的左儿子编号和右儿子编号。

输出格式

输出一行，一个整数，表示所有子树中完全二叉树的数量。

输入输出样例

输入 #1

4
2 3
4 0
0 0
0 0

输出 #1

4

输入 #2

4
2 3
0 0
4 0
0 0

输出 #2

3

说明/提示

对于 40% 的测试点，保证 1≤n≤500。

对于所有测试点，保证 1≤n≤10^5。

思路：

        这是一道经典的树形DP。状态：DP[i]为1是完全二叉树，DP[i]为2是满二叉树，DP[i]为0代表啥也不是。不难发现，满二叉树一定是完全二叉树。

当这个节点的左子树为满二叉树时，并且右子树为高度和左子树一样的满二叉树时，以这个节点为根的子树也为满二叉树。

当这个节点的左子树为满二叉树时，并且右子树为高度和左子树一样的完全二叉树时，以这个节点为根的子树为完全二叉树。

当这个节点的左子树为满二叉树或完全二叉树时，并且右子树为高度等于左子树高度减一的满二叉树时，以这个节点为根的子树为完全二叉树。

代码：

#include <bits/stdc++.h>
#include <bits/c++config.h>
#include <ostream>
#include <istream>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <math.h>
#include <time.h>
#include <ctime>
#include <cstdlib>

#define ll long long
#define ull unsigned long long
#define db double
#define st string
#define ch char
#define bo bool
#define s1 27
#define s2 205
#define s3 2005
#define s4 20005
#define s5 200005
#define s6 2000005
#define s7 20000005

using namespace std;
struct tree{
int l,r;
}a[s5];
int n,dp[s5],h[s5];
ll ans;
void dfs(int u,int d){
h[u]=d;
if(a[u].l!=0) dfs(a[u].l,d+1);
if(a[u].r!=0) dfs(a[u].r,d+1);
if(a[u].l!=0) h[u]=max(h[u],h[a[u].l]);
if(a[u].r!=0) h[u]=max(h[u],h[a[u].r]);
if(a[u].l==0&&a[u].r==0) dp[u]=2;
else if(a[u].r==0&&h[a[u].l]==d+1) dp[u]=1;
else if(dp[a[u].l]==2&&dp[a[u].r]==2&&h[a[u].l]==h[a[u].r]) dp[u]=2;
else if(dp[a[u].l]==2&&dp[a[u].r]==1&&h[a[u].l]==h[a[u].r]) dp[u]=1;
else if(dp[a[u].l]>=1&&dp[a[u].r]==2&&h[a[u].l]==h[a[u].r]+1) dp[u]=1;
if(dp[u]>=1) ans++;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].l>>a[i].r;
}
dfs(1,1);
cout<<ans;
// for(int i=1;i<=n;i++){
// cout<<h[i]<<' ';
// }
return 0;
}

补充：

完全二叉树与满二叉树的定义

完全二叉树：
除最后一层外，其他层的节点数均达到最大值，且最后一层的节点从左到右连续排列。若最后一层不满，则缺失的节点只能出现在右侧。
数学性质：

• 高度为 ( h ) 的完全二叉树，节点数 ( n ) 满足 ( 2^{h-1} \\leq n < 2^h )。
• 编号为 ( i ) 的节点，其左子节点编号为 ( 2i )，右子节点为 ( 2i+1 )（假设根节点编号为 1）。

满二叉树：
每一层的节点数均达到最大值，即所有非叶子节点均有左右子节点。
数学性质：

• 高度为 ( h ) 的满二叉树，节点总数 ( n = 2^h – 1 )。
• 叶子节点全部位于最后一层，数量为 ( 2^{h-1} )。

C++ 实现与判断方法

完全二叉树的判断

通过层序遍历检查节点是否连续，无中间空缺：

#include <queue>
using namespace std;

struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool isCompleteTree(TreeNode* root) {
if (!root) return true;
queue<TreeNode*> q;
q.push(root);
bool hasNull = false;

while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (!node) {
hasNull = true;
} else {
if (hasNull) return false; // 发现非空节点出现在空节点后
q.push(node->left);
q.push(node->right);
}
}
return true;
}

满二叉树的判断

递归验证所有非叶子节点均有左右子节点：

bool isFullTree(TreeNode* root) {
if (!root) return true;
if (!root->left && !root->right) return true; // 叶子节点
if (root->left && root->right)
return isFullTree(root->left) && isFullTree(root->right);
return false; // 仅有一个子节点
}

应用场景

• 完全二叉树：优先用于堆结构（如优先队列），空间利用率高且易于数组存储。
• 满二叉树：常见于完美平衡的场景，如某些数学计算或哈夫曼编码的中间状态。

关键区别总结