首页 > 其他分享 >嘤嘤的新平衡树

嘤嘤的新平衡树

时间:2022-12-23 22:45:49浏览次数:33  
标签:结点 int height 二叉树 ans 平衡 root

给定一棵二叉树,二叉树的每个结点只有0或2个孩子。
你需要对每个结点赋值一个正整数,使得每个结点的左右子树权值和相等。
你需要返回所有结点的最小权值和对 109+7 取模的结果。
二叉树结点个数不超过105

输入
{0,0,0}
输出
3

每个节点只有0或2个孩子,那么这棵树就一定是一颗满二叉树

可以是这个样子,但是不应该考虑节点的赋值,而是把它看作是一颗收起来的左右对称的满二叉树,然后需要做的就是求这个满二叉树的节点和

int height(TreeNode* root) {
	// 获取树的层数
	if (!root) return 0;
	return max(height(root->left), height(root->right)) + 1;
}

int getTreeSum(TreeNode* tree) {
	int ans = 1, k = height(tree),mod = 1e9+7;
	while (k--) ans *= 2, ans %= mod;
	return ans - 1;
}

标签:结点,int,height,二叉树,ans,平衡,root
From: https://www.cnblogs.com/yaocy/p/17001767.html

相关文章

  • #yyds干货盘点# LeetCode程序员面试金典:检查平衡性
    题目:实现一个函数,检查二叉树是否平衡。在这个问题中,平衡树的定义如下:任意一个节点,其两棵子树的高度差不超过1。示例1:给定二叉树[3,9,20,null,null,15,7]  3 /\......
  • R语言统计学DOE实验设计:用平衡不完全区组设计(BIBD)分析纸飞机飞行时间实验数据
    全文链接:http://tecdat.cn/?p=31010原文出处:拓端数据部落公众号平衡不完全区组设计(BIBD)是一个很好的研究实验设计,具有从统计的角度看各种所需的特征。最近我们被要求撰......
  • P3369 【模板】普通平衡树
    题目链接题目要求:插入数据,删除数据,查询数的排名,查询排名为x的数,找前驱,找后继旋转操作,左旋和右旋,旋转$x$,旋转操作一定要符合先序遍历前后一致voidrotate(intx){ ......
  • 玩转OpenHarmony PID:教你打造两轮平衡车
     简介此次为大家带来的是OpenAtomOpenHarmony(以下简称“OpenHarmony”)系统与PID控制算法相结合并落地的平衡车项目。PID控制算法是一种经典的,并被广泛应用在控制领......
  • 各种平衡树
    如题,就是各种平衡树。FHQTreapAC记录#include<bits/stdc++.h>usingnamespacestd;intQread(){ intx=0;boolf=false;charch=getchar(); while(ch<'0'||ch>'9......
  • C/C++简易图书管理模拟系统(二叉平衡树)
    C/C++简易图书管理模拟系统(二叉平衡树)C/C++简易图书管理模拟系统(二叉平衡树)数据结构课程实验教案第8页实验题目八:综合实验简易图书管理模拟系统 机时......
  • 平衡二叉树(java版)
    题目描述:标签:树深度优先搜索递归给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值......
  • 深度学习炼丹-不平衡样本的处理
    目录​​前言​​​一,数据层面处理方法​​​1.1,数据扩充​​​1.2,数据(重)采样​​​数据采样方法总结​​​​1.3,类别平衡采样​​​二,算法(损失函数)层面处理方法​​​2.1,Fo......
  • 算法9:LeetCode_给定一个二叉树,判断它是否是高度平衡的二叉树。
    我们在算法7中已经学习了二叉排序树,平衡二叉树的相关知识。既然我们知道平衡二叉树中,节点的左子树和右子树的高度差至多为1,那么我们就可以通过如下思路来进行判断。1.节......
  • 算法7:平衡二叉树(AVLTree)
    二叉排序树(BST,BinarySortTree)也称二叉查找树(BinarySearchTree),或二叉搜索树。定义:一颗二叉树,满足以下属性:左子树的所有的值小于根节点的值右子树的所有值大于根......