首页 > 其他分享 >计算二叉树(二叉链表)的带权路径长度

计算二叉树(二叉链表)的带权路径长度

时间:2024-11-11 23:31:18浏览次数:1  
标签:lc int data 链表 带权 二叉树 rc root getit


方法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

相关文章

  • AcWing 1626:链表元素分类 ← 单链表
    【题目来源】https://www.acwing.com/problem/content/1628/【题目描述】给定一个单链表,请编写程序将链表元素进行分类排列,使得所有负值元素都排在非负值元素的前面,而[0,K]区间内的元素都排在大于K的元素前面。但每一类内部元素的顺序是不能改变的。例如:给定链表为18→......
  • 101. 对称二叉树
    题目链接解题思路检查一个二叉树是否轴对称,其实和根结点无关,而是和其左右子树有关。左子树头等于右子树头,然后递归调用,「左子树的右儿子」要等于「右子树的左儿子」并且「左子树的左儿子」要等于「右子树的左儿子」。代码/***Definitionforabinarytreenode.......
  • 代码随想录——二叉树-12.平衡二叉树
    自顶向下递归(前序遍历)这种方法是一开始想到的,虽然ac了但是对于它的本质却不清不楚,不知道时间复杂度,不知道属于前序遍历。思路首先得到root节点的左右子树的深度(左右),若深度差绝对值大于1(中),则root为根的树不是平衡二叉树;否则继续递归root的左右子树,其左右子树都是平衡二叉树......
  • 代码随想录——二叉树-11.完全二叉树的节点个数
    思路一、层序遍历,时间复杂度O(n)二、利用完全二叉树性质,时间复杂度O(logn*logn)(小于O(n))完全二叉树性质:若树深度为h,则前h-1层节点都达到最大值。第h层节点都集中在最左侧的位置完全二叉树要么1.是满二叉树2.最后一层没满满二叉树计算节点数太方便了,直接用公式2^h-1。......
  • 随机链表 (Randomized Linked List)、随机树 (Randomized Tree)详细解读
    一、随机化数据结构(RandomizedDataStructures)随机化数据结构是通过引入随机性来优化传统数据结构的性能,特别是在最坏情况性能表现较差时。通过随机化,许多原本具有较差时间复杂度的操作可以实现平均O(1)或O(logn)的时间复杂度,减少了最坏情况下的复杂度。常见的随机......
  • 【模板】如何实现链表元素的反转
    反转链表是链表操作中一个经典的问题,也是面试中常见的考题。本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作。我们将使用C++代码演示具体实现,同时分析时间复杂度和空间复杂度。问题定义给定一个单链表,我们需要将链表的节点顺序反转。例如,链表1......
  • 数据结构 ——— 链式二叉树oj题:对称二叉树
    目录题目要求手搓一个对称二叉树代码实现 题目要求给你一个二叉树的根节点 root ,检查它是否轴对称手搓一个对称二叉树代码演示://数据类型typedefintBTDataType;//二叉树节点的结构typedefstructBinaryTreeNode{ BTDataTypedata;//每个节点的数据......
  • 实现链式结构二叉树
    目录需要实现的操作链式结构二叉树实现结点的创建前序遍历中序遍历后序遍历计算结点个数计算二叉树的叶子结点个数 计算二叉树第k层结点个数计算二叉树的深度查找值为x的结点 销毁层序遍历判断是否为完全二叉树 总结需要实现的操作//前序遍历voidPreOr......
  • 每日一题之二叉树
    已知结点元素值为正整数且值不相同的一棵二叉树。该二叉树通过给出其先序遍历序列和中序遍历序列构造而成。输入一个整数x,针对此二叉树编写程序求出x的右子树中所有结点值的和(若x不在树上,输出-1)。 输入说明:第一行输入某二叉树的先序遍历序列第二行输入该二叉树的中序遍历......
  • 根据二叉树创建字符串
    题目:606.根据二叉树创建字符串-力扣(LeetCode)给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串。空节点使用一对空括号对 "()" 表示,转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空......