方法1
#include <bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
using pii = pair<int, int>;
typedef struct Btnode {
int data;
struct Btnode *lc,*rc;
}*Btree,Btnode ;
//笔试这个可以放上面,但是真的写程序 应该把getwpl放在getit下面
void getwpl(Btree root ,int dep)
{
getit(root,0);
}
//计算带权路径和 所有叶子结点的带权路径长度和
int getit(Btree root,int dep)
{
if(! root->lc && !root -> rc) return dep*(root->data);//叶子点
else {
return getit(root->lc,dep+1)+getit(root->rc,dep+1);//递归进左右子树
}
}
方法2
#include <bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
using pii = pair<int, int>;
typedef struct Btnode {
int data;
struct Btnode *lc,*rc;
}*Btree,Btnode ;
void getwpl(Btree root ,int dep)
{
getit(root,0);
}
//所有非叶子结点的权值之和
int getit(Btree root)
{
if( !root->lc && !root->rc ) return 0;
else {
int wl=getit(root->lc);
int wr=getit(root->rc);
root->data=root->lc->data+root->rc->data;
//不断从底层更新每个非叶子结点的权值,直到回到根节点
return wl+wr+root->data;
}
}
标签:lc,int,data,链表,带权,二叉树,rc,root,getit
From: https://www.cnblogs.com/swjswjswj/p/18540808