1. 如何构建父节点与子节点的关系
通过一个结构体,包括每一个节点的父、子节点,在读入一个节点的数据时,标记其子节点的父节点为自己
2. 代码
#include<bits/stdc++.h>
using namespace std;
struct node
{
int f,l,r,w;
}tr[105];
int n,s,ans=0x3f3f3f3f,vis[105];
void dfs(int pos,int stp)
{
int fa=tr[pos].f,le=tr[pos].l,ri=tr[pos].r;
s+=tr[pos].w*stp;
if (fa && !vis[fa]) // 在每一个递归前加是否进入递归的判断条件
{
vis[fa]=1;
dfs(fa,stp+1);
}
if (le && !vis[le]) // 在有多条件的情况下 比在函数内部最开头统一判断 条理更清晰
{
vis[le]=1;
dfs(le,stp+1);
}
if (ri && !vis[ri])
{
vis[ri]=1;
dfs(ri,stp+1);
}
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>tr[i].w>>tr[i].l>>tr[i].r;
tr[tr[i].l].f=i; // 子节点的父节点为此时i值,构建与父节点的关系
tr[tr[i].r].f=i;
}
for (int i=1;i<=n;i++)
{
s=0; // 每次循环都要保证s为0的初始值
memset(vis,0,sizeof(vis)); // 及时清零标记数组 养成好习惯
vis[i]=1;
dfs(i,0);
ans=min(ans,s);
}
cout<<ans;
return 0;
}