JAVA程序设计:完全二叉树插入器(LeetCode:919)

news/2024/10/30 21:27:27/

完全二叉树是每一层(除最后一层外)都是完全填充(即,结点数达到最大)的,并且所有的结点都尽可能地集中在左侧。

设计一个用完全二叉树初始化的数据结构 CBTInserter,它支持以下几种操作:

CBTInserter(TreeNode root) 使用头结点为 root 的给定树初始化该数据结构;
CBTInserter.insert(int v) 将 TreeNode 插入到存在值为 node.val = v  的树中以使其保持完全二叉树的状态,并返回插入的 TreeNode 的父结点的值;
CBTInserter.get_root() 将返回树的头结点。
 

示例 1:

输入:inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
输出:[null,1,[1,2]]
示例 2:

输入:inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
输出:[null,3,4,[1,2,3,4,5,6,7,8]]
 

提示:

最初给定的树是完全二叉树,且包含 1 到 1000 个结点。
每个测试用例最多调用 CBTInserter.insert  操作 10000 次。
给定结点或插入结点的每个值都在 0 到 5000 之间。

思路:我们标记最下边一层需要放多少个和已经放了多少个,若放满了就再加一层,对于具体放在最底层的那个位置,我们考虑类似于二分查找的模式,例如:最底层放满需要8个元素,目前已经放了5个了,现在需要放第六个元素。则第一次应该走到根节点的右子树,因为左子树的最底层最多也只能放4个元素,则我们将右子树的树根当做根节点,而因为左子树已经包含了4个元素,因此在当前子树中最底层只用将待插元素放在第6-4个位置上即可,其实你可以发现问题已经归结为子问题了,进一下向下也是一样的。

class CBTInserter {int sum;int size=0,nowNum;TreeNode root,start;public CBTInserter(TreeNode root) {sum=0;start=root;this.root=root;dfs(this.root);int len=0,sm=0;while(sm+(1<<len)<=sum) {sm+=1<<len;len++;}root=start;nowNum=sum-sm+1;	size=1<<len;}private void dfs(TreeNode root) {if(root==null) return;sum++;dfs(root.left);dfs(root.right);}public int insert(int v) {root=start;int tmp1=nowNum,tmp2=size;while(root!=null) {if(tmp1>tmp2/2) {tmp1-=tmp2/2;if(tmp2>2)root=root.right;else {root.right=new TreeNode(v);break;}}else {if(tmp2>2)root=root.left;else {root.left=new TreeNode(v);break;}}tmp2/=2;}if(nowNum==size) {size*=2;nowNum=1;}elsenowNum++;return root.val;}public TreeNode get_root() {return start;}
}

 


http://www.ppmy.cn/news/332834.html

相关文章

软考高级架构师笔记-6计算机系统性能评价信息系统基础知识

目录 1. 前言 & 考情分析2. 系统配置与性能评价1. 性能指标2. 性能指标3. 阿姆达尔解决方案3.信息系统基础知识1.信息系统的分类2.信息系统的生命周期3.信息系统战略规划3.常见系统介绍1.客户关系管理CRM2.供应链管理SCM3.企业应用集成EAI4.结语1. 前言 & 考情分析 前…

springboot使用sm2加密传输

加密原理&#xff1a; 使用sm2生成一对公钥和私钥。然后将公钥发送给前端&#xff0c;私钥自己在后端进行保存&#xff08;本次示例是将私钥保存在redis中&#xff0c;因为redis是使用键值对进行保存数据的&#xff0c;所以还需要生成一个uuid进行保存和获取密钥数据。&#x…

国密SSL协议的Android JSSE实现 大宝CA Android版本 国密SSL身份识别与双向认证

系统要求 Android 7.0&#xff08;API 24&#xff09;及以上 功能介绍 单向认证接收并显示服务器端国密数字证书使用PP软件授权平台获取授权数据的简要说明 核心代码 //这里写入子线程需要做的工作 try { …

pos密事(续2)

紧接上文&#xff0c;本篇简述mac值的计算以及PIN(个人工作秘钥)的加密以及转加密。 信息&#xff1a;就用上文算出来的PIN和PAK PIN秘钥明文 B42C67015B2FA5B85135D170A2ECC4E5 PAK秘钥明文 7C8B366BD1C56183655F8D3529A2117B3.MAC密钥的计算(国密和国际) 数据 0200602406C0…

分析网站登录处的加密算法(二)

前言&#xff1a;在渗透测试过程中&#xff0c;我们经常会碰到登录处用js加密字段的情况。在大多数情况下&#xff0c;看到这种加密方式&#xff0c;我们都会放弃对该登录处进行暴力破解。本文主要讲解对js加密进行绕过&#xff0c;以达到爆破或绕反爬的目的&#xff01; 对登录…

加密算法整理(哈希SHA, 奇偶校验, DES, 3DES, 3DES 分散, MAC, RSA, SM2) 持续更新

现有加密算法&#xff1a; 对称算法&#xff1a;DES / 3DES / SM4 / AES / SSF33 / RCX 非对称算法&#xff1a; RSA / SM2 / ECC / DSA / DH 信息摘要算法&#xff1a; SHA1 / SM3 / MD4 / MD5 / SHA256 目前银联规范银行卡中使用的安全加密算法分为两种&#xff1a;国际算…

Sm-DOTA DOTA修饰稀土钐 Sm-DTPA二亚乙基三胺五乙酸修饰稀土钐

Sm-DOTA DOTA修饰稀土钐 Sm-DTPA二亚乙基三胺五乙酸修饰稀土钐 镧系元素&#xff08;有时称为稀土元素&#xff09;是元素周期表中从原子序数57&#xff08;镧&#xff09;到71的14个“ f嵌段”元素的集合。其中&#xff0c;euro&#xff08;Eu&#xff09;&#xff0c;&#x…

国密算法 SM2 公钥加密 非对称加密 数字签名 密钥协商 python实现完整代码

SM2算法是国家密码管理局于2010年12月颁布的中国商用公钥密码标准算法。SM2基于椭圆曲线离散对数问题&#xff0c;计算复杂度是指数级&#xff08;暂未发现亚指数级或多项式级的计算方法&#xff09;&#xff0c;相较于广泛应用的RSA公钥密码算法&#xff0c;在同等安全程度要求…