企业官网建设流程全解析

【算法刷题】二叉树的黄金指数之和（DFS深度优先搜索）

平台：蓝桥网 / 算法竞赛
考点：二叉树遍历、深度优先搜索（DFS）、数据类型溢出防护、1-based 下标映射

📌 1. 题目描述

给定一棵包含nnn个节点的二叉树，节点编号为1∼n1 \sim n1∼n，其中111号节点为根节点。第iii个节点的权重为wiw_iwi​。

请你计算出这棵树中黄金指数为000的所有节点的权重之和。

黄金指数定义：

1. 根节点的黄金指数为000。
2. 若一个节点是其父节点的左儿子，则它的黄金指数 = 父节点的黄金指数+1+ 1+1。
3. 若一个节点是其父节点的右儿子，则它的黄金指数 = 父节点的黄金指数−1- 1−1。

💡 2. 解题思路

1. 结构存储：

   • 使用数组left_child[i]和right_child[i]存储每个节点iii的左右子节点编号（如果值为000表示对应位置为空）。
   • 使用数组weight[i]存储节点iii的权重。

2. DFS 状态传递：

   • 从根节点111开始递归，函数定义为dfs(u, gold_index)，其中u为当前节点编号，gold_index为到达当前节点时的黄金指数。
   • 每访问到一个节点，若gold_index == 0，则将当前节点权重weight[u]累加至全局变量ans中。
   • 向左递归遍历时，指数传递为gold_index + 1；
   • 向右递归遍历时，指数传递为gold_index - 1。

3. 复杂度和防错策略：

   • 时间复杂度：O(n)\mathcal{O}(n)O(n)，每个节点仅访问一次。
   • 空间复杂度：O(n)\mathcal{O}(n)O(n)，主要为递归栈深度与树的存储空间。
   • 数据类型：节点权重累加和ans需使用long long类型，避免多节点权重累加时发生整型溢出。

⚠️ 3. 易错点总结

1. 数组下标与编号对齐（1-based Indexing）：
   • 节点编号为1∼n1 \sim n1∼n，输入循环必须从i=1i = 1i=1到i=ni = ni=n，切勿使用i=0i = 0i=0到i=n−1i = n - 1i=n−1，否则会导致权重与节点编号错位。
2. 累加对象错误：
   • 当判定gold_index == 0时，应该加的是weight[u]，而非gold_index。
3. 右子树的方向计算：
   • 往右走是黄金指数−1-1−1，不要误写成+1+1+1。

💻 4. C++ 完整代码

#include<iostream>usingnamespacestd;constintMAXN=100005;intweight[MAXN];intleft_child[MAXN];intright_child[MAXN];longlongans=0;// 存储权重总和，防止爆 int// DFS 深度优先搜索voiddfs(intu,intgold_index){if(u==0)return;// 当黄金指数为 0 时，累加当前节点的权重if(gold_index==0){ans+=weight[u];}// 遍历左子树，黄金指数 +1if(left_child[u]!=0){dfs(left_child[u],gold_index+1);}// 遍历右子树，黄金指数 -1if(right_child[u]!=0){dfs(right_child[u],gold_index-1);}}intmain(){// 开启 IO 优化，提升读写效率ios::sync_with_stdio(false);cin.tie(nullptr);intn;if(!(cin>>n))return0;// 读取每个节点的权重（下标从 1 到 n）for(inti=1;i<=n;i++){cin>>weight[i];}// 读取左右儿子节点（下标从 1 到 n）for(inti=1;i<=n;i++){cin>>left_child[i]>>right_child[i];}// 从根节点 1 开始遍历，初始黄金指数为 0dfs(1,0);// 输出最终答案cout<<ans<<"\n";return0;}