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

题意给定一棵包含 n 个结点的有根二叉树结点依次以 1,2,…,n 编号根结点编号为 1。对于结点 i其左儿子的编号记为 li​右儿子编号记为 ri​。特别地如果左儿子不存在则 li​0如果右儿子不存在则 ri​0。树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 n 棵子树中有多少棵子树是完全二叉树。输入格式第一行一个正整数 n表示有根二叉树结点数量。接下来 n 行每行两个正整数 li​,ri​表示结点 i 的左儿子编号和右儿子编号。输出格式输出一行一个整数表示所有子树中完全二叉树的数量。本题思路这是一道树形DP。dp[i] 表示 以i为根的二叉树是什么种类的二叉树。dp[i] 0 表示以i为根的二叉树是普通二叉树。dp[i] 1 表示以i为根的二叉树是完全二叉树。dp[i] 2 表示以i为根的二叉树是满二叉树。此外还需要进行多层判断。if(a[u].l 0 a[u].r 0dp[i] 2else if(a[u].l a[u].r 0 从a[u].l往下最多深度 这棵树的深度 1dp[i] 1有三种情况可以使以i为根的二叉树是完全二叉树。一左边是满二叉树或完全二叉树右边是满二叉树左深度 比右深度大1二左右深度相同 左边是满二叉树右边是满二叉树三左右深度相同 左边是满二叉树右边是完全二叉树代码#includebits/stdc.h using namespace std; #define N 1000005 int dp[N], h[N]; struct node{ int l, r; }; node a[N]; int n, ans 0; void dfs(int u, int deepth) { h[u] deepth; if (a[u].l) { dfs(a[u].l, deepth 1); h[u] max(h[u], h[a[u].l]); } if (a[u].r) { dfs(a[u].r, deepth 1); 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].l a[u].r 0 h[a[u].l] deepth 1) dp[u] 1; else { if (h[a[u].l] h[a[u].r]) { if (dp[a[u].l] 2 dp[a[u].r] 2) dp[u] 2; else if (dp[a[u].l] 2 dp[a[u].r] 1) dp[u] 1; } else if (h[a[u].l] h[a[u].r] 1) if (dp[a[u].l] 0 dp[a[u].r] 2) dp[u] 1; } ans (dp[u] 0); } int main () { cin n; for (int i 1; i n; i ) cin a[i].l a[i].r; dfs(1, 0); cout ans; return 0; }