【题目来源】洛谷P17013 [GESP202606 六级] 满二叉树 - 洛谷【题目描述】给定一棵包含n nn个结点的有根二叉树结点依次以1 , 2 , … , n 1, 2, \dots, n1,2,…,n编号根结点编号为1 11。对于结点i ii其左儿子的编号记为l i l_ili​右儿子编号记为r i r_iri​。特别地如果左儿子不存在则l i 0 l_i 0li​0如果右儿子不存在则r i 0 r_i 0ri​0。树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有n nn棵子树中有多少棵子树是满二叉树。满二叉树是指所有叶子深度均相同且除叶子外均有两个儿子的二叉树例如以下三棵二叉树均是满二叉树() () () / \ / \ () () () () / \ / \ () ()() ()在上面这棵有3 33个节点的二叉树中有3 33个子树是满二叉树包括整个树本身及所有的单个叶子节点又例如(1) / \ (2) (3) / \ (4) (5)在上面这棵有5 55个节点的二叉树中有4 44个子树是满二叉树包括节点3 33的子树以及所有单个叶子节点。【输入】第一行一个正整数n nn表示有根二叉树结点数量。接下来n nn行每行两个非负整数l i , r i l_i, r_ili​,ri​表示结点i ii的左儿子编号和右儿子编号整数之间以空格分隔。【输出】输出一行一个整数表示所有子树中满二叉树的数量。【输入样例】4 2 3 4 0 0 0 0 0【输出样例】2【核心思想】问题分析给定一棵有根二叉树需要统计所有子树中满二叉树的数量。满二叉树的定义是所有叶子深度相同且每个非叶子结点都有两个儿子。这是一个**树形动态规划 深度优先搜索DFS**问题核心在于自底向上判断每个子树是否满足满二叉树的两个条件。算法选择深度优先搜索DFS从根结点开始递归遍历先处理子结点再处理父结点实现自底向上的信息传递状态标记每个结点维护两个状态——f l a g [ x ] flag[x]flag[x]是否为满二叉树和d e p [ x ] dep[x]dep[x]子树高度/叶子深度关键步骤叶子结点判定l x 0 l_x 0lx​0且r x 0 r_x 0rx​0f l a g [ x ] ← t r u e flag[x] \leftarrow trueflag[x]←true单个叶子结点是满二叉树d e p [ x ] ← 1 dep[x] \leftarrow 1dep[x]←1叶子高度为1 11a n s ← a n s 1 ans \leftarrow ans 1ans←ans1递归处理子树若左儿子存在则d f s ( l x ) dfs(l_x)dfs(lx​)若右儿子存在则d f s ( r x ) dfs(r_x)dfs(rx​)满二叉树判定以x xx为根的子树条件f l a g [ l x ] t r u e flag[l_x] trueflag[lx​]true且f l a g [ r x ] t r u e flag[r_x] trueflag[rx​]true且d e p [ l x ] d e p [ r x ] dep[l_x] dep[r_x]dep[lx​]dep[rx​]满足时f l a g [ x ] ← t r u e flag[x] \leftarrow trueflag[x]←trued e p [ x ] ← d e p [ l x ] 1 dep[x] \leftarrow dep[l_x] 1dep[x]←dep[lx​]1a n s ← a n s 1 ans \leftarrow ans 1ans←ans1非满二叉树处理f l a g [ x ] ← f a l s e flag[x] \leftarrow falseflag[x]←falsed e p [ x ] ← max ⁡ ( d e p [ l x ] , d e p [ r x ] ) 1 dep[x] \leftarrow \max(dep[l_x], dep[r_x]) 1dep[x]←max(dep[lx​],dep[rx​])1输出结果a n s ansans时间/空间复杂度时间复杂度O ( n ) O(n)O(n)每个结点仅访问一次每次处理为O ( 1 ) O(1)O(1)空间复杂度O ( n ) O(n)O(n)递归栈深度最坏为O ( n ) O(n)O(n)数组存储为O ( n ) O(n)O(n)树形 DP 与 DFS 的核心思想自底向上信息聚合通过 DFS 后序遍历先获取子结点的f l a g flagflag和d e p depdep信息再判断父结点是否满足满二叉树条件确保子问题已解决满二叉树的递归定义一棵子树是满二叉树当且仅当左右子树都是满二叉树且高度相同。这一定义天然适合递归判断高度统一性d e p [ x ] dep[x]dep[x]表示以x xx为根的子树中叶子到x xx的最大距离满二叉树要求左右子树高度严格相等保证所有叶子深度一致计数策略在判定每个结点为满二叉树时立即累加a n s ansans利用 DFS 遍历所有子树自然统计所有满足条件的子树适用于树形结构的递归性质判定、自底向上状态传递类问题【算法标签】#普及- #DFS-树【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN100005;// 常量最大结点数intn;// n: 二叉树结点数量intans;// ans: 满二叉树子树的数量intl[N],r[N];// l[i]: 结点 i 的左儿子编号; r[i]: 结点 i 的右儿子编号intdep[N];// dep[i]: 以结点 i 为根的子树高度叶子深度boolflag[N];// flag[i]: 以结点 i 为根的子树是否为满二叉树voiddfs(intx)// 深度优先搜索计算以 x 为根的子树信息{if(l[x]0r[x]0)// 叶子结点左右儿子都不存在{flag[x]true;// 单个叶子结点是满二叉树dep[x]1;// 叶子结点的高度为 1ans;// 满二叉树计数加一return;}if(l[x]!0)// 如果左儿子存在dfs(l[x]);// 递归计算左子树if(r[x]!0)// 如果右儿子存在dfs(r[x]);// 递归计算右子树// 判断以 x 为根的子树是否为满二叉树// 条件左右子树都是满二叉树且左右子树高度相同if(flag[l[x]]1flag[r[x]]1dep[l[x]]dep[r[x]]){flag[x]1;// 标记为满二叉树dep[x]dep[l[x]]1;// 当前子树高度 子树高度 1ans;// 满二叉树计数加一}else// 不是满二叉树{flag[x]0;// 标记为非满二叉树dep[x]max(dep[l[x]],dep[r[x]])1;// 高度取左右子树的最大值}}signedmain(){cinn;// 读入结点数量for(inti1;in;i)// 读入每个结点的左右儿子编号{cinl[i]r[i];}dfs(1);// 从根结点开始 DFScoutansendl;// 输出满二叉树子树的总数return0;}【运行结果】4 2 3 4 0 0 0 0 0 2