当前位置:网站首页>2022.08.05_每日一题
2022.08.05_每日一题
2022-08-09 18:00:00 【诺.い】
623. 在二叉树中增加一行
题目描述
给定一个二叉树的根 root
和两个整数 val
和 depth
,在给定的深度 depth
处添加一个值为 val
的节点行。
注意,根节点 root
位于深度 1
。
加法规则如下:
- 给定整数
depth
,对于深度为depth - 1
的每个非空树节点cur
,创建两个值为val
的树节点作为cur
的左子树根和右子树根。 cur
原来的左子树应该是新的左子树根的左子树。cur
原来的右子树应该是新的右子树根的右子树。- 如果
depth == 1
意味着depth - 1
根本没有深度,那么创建一个树节点,值val
作为整个原始树的新根,而原始树就是新根的左子树。
示例 1:
输入: root = [4,2,6,3,1,5], val = 1, depth = 2
输出: [4,1,1,2,null,null,6,3,1,5]
示例 2:
输入: root = [4,2,null,3,1], val = 1, depth = 3
输出: [4,2,null,1,1,3,null,null,1]
提示:
- 节点数在
[1, 104]
范围内 - 树的深度在
[1, 104]
范围内 -100 <= Node.val <= 100
-105 <= val <= 105
1 <= depth <= the depth of tree + 1
coding
1.深度优先
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
int val;
int depth;
public TreeNode addOneRow(TreeNode root, int val, int depth) {
this.val = val;
this.depth = depth;
if(depth == 1){
return new TreeNode(val, root, null);
}
dfs(root, 1);
return root;
}
public void dfs(TreeNode node, int curDepth){
if(curDepth == depth - 1){
if(node != null){
node.left = new TreeNode(val, node.left, null);
node.right = new TreeNode(val, null, node.right);
}
return;
}
if (node != null){
dfs(node.left, curDepth + 1);
dfs(node.right, curDepth + 1);
}
}
}
2.广度优先
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
if(depth == 1){
return new TreeNode(val, root, null);
}
List<TreeNode> temp1 = new ArrayList<>();
temp1.add(root);
for (int i = 1; i < depth - 1; i ++) {
List<TreeNode> temp2 = new ArrayList<>();
for(TreeNode node : temp1) {
if (node.left != null) {
temp2.add(node.left);
}
if (node.right != null) {
temp2.add(node.right);
}
}
temp1 = temp2;
}
for(TreeNode node : temp1) {
node.left = new TreeNode(val, node.left, null);
node.right = new TreeNode(val, null, node.right);
}
return root;
}
}
边栏推荐
- [免费专栏] Android安全之APK动态方式逆向应用【三种Smali注入方法】
- fastdfs-client使用
- Bi Sheng Compiler Optimization: Lazy Code Motion
- LeetCode笔记:Weekly Contest 305
- 商业智能BI行业分析思维框架:铅酸蓄电池行业(一)
- 从功能测试到自动化测试你都知道他们的有缺点吗?
- 与同步传递相关的获取-释放序列
- Office 365 Group概述以及创建方法
- What is the Treasure Project (TPC), a dark horse with wings in 2022!
- 牛客网 Verilog 在线编程题库解答(VL1~VL10)
猜你喜欢
JMeter压测时如何在达到给定错误数量后停止测试
IMX6ULL—汇编LED灯
qq机器人账号不能发送群消息,被风控
How to play with container local storage through open-local? | Dragon Lizard Technology
智驾科技完成C1轮融资,此前2轮已融4.5亿元
loadrunner脚本--参数化
Paper sharing: "FED BN" uses the LOCAL BATCH NORMALIZATION method to solve the Non-iid problem
100+开箱即用的AI工具箱;程序员150岁长寿指南;『地理空间数据科学』课程资料;Graphic数据可视化图表库;前沿论文 | ShowMeAI资讯日报
VIT transformer详解
16 张图解 | 淘宝 10年架构演进
随机推荐
[免费专栏] Android安全之和平精英(FZ)APK逆向分析
五种常用的排序方法
numpy中nan_to_num如何使用
[免费专栏] Android安全之ZIP文件目录遍历漏洞
OpenHarmony如何查询设备类型
winpe工具WEPE微PE工具箱
ceph 创建池和制作块设备基操
[免费专栏] Android安全之动态代码注入技术(利用JDB调试APK)
全自动化机器学习建模!效果吊打初级炼丹师!
字节二面:可重复读隔离级别下,这个场景会发生什么?
牛客网 Verilog 在线编程题库解答(VL1~VL10)
C语言知识补充
C#/VB.NET:从PowerPoint文档中提取文本和图片
混动产品助力,自主SUV市场格局迎来新篇章
重定向操作
论文精读:VIT - AN IMAGE IS WORTH 16X16 WORDS: TRANSFORMERS FOR IMAGE RECOGNITION AT SCALE
Ros简介
国产抗新冠口服药每瓶不超300元/ 我国IPv6网络全面建成/ 谷歌入局折叠屏手机...今日更多新鲜事在此...
loadrunner script -- parameterization
宝塔面板安装使用