LeetCode-Go 题解 623Add One Row to Tree二叉树指定深度插入一行【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文讲解 LeetCode 第 623 题「Add One Row to Tree」给树添加一行在 LeetCode-Go 仓库中的完整题解。本题要求在二叉树指定的深度d处插入一行值为v的新节点同时保持原有子树的相对位置不变并需正确处理d 1替换根节点与d超过树高在最深层叶子之下追加两种边界情况。读完本文你将掌握基于 DFS 的前序遍历插入解法、两个关键特殊分支的判定逻辑以及该解法对应的单元测试与复杂度分析可直接迁移到其他按层改造二叉树的问题中。题目描述给定一棵二叉树的根节点root以及值v和深度d需要在深度d处添加一行值为v的节点。根节点所在深度记为 1。添加规则给定正整数深度d针对深度d-1层的每一个非空节点 N为 N 创建两个值为v的新节点分别作为 N 的左子树根和右子树根。同时N 的原左子树整体挂到新左子树根的左子树上N 的原右子树整体挂到新右子树根的右子树上。如果d 1说明深度d-1根本不存在此时直接创建一个值为v的新节点作为整棵树的新根原树整体作为新根的左子树。示例 1Input: A binary tree as following: 4 / \ 2 6 / \ / 3 1 5 v 1, d 2 Output: 4 / \ 1 1 / \ 2 6 / \ / 3 1 5示例 2Input: A binary tree as following: 4 / 2 / \ 3 1 v 1, d 3 Output: 4 / 2 / \ 1 1 / \ 3 1注意事项给定的d取值范围为[1, 树的最大深度 1]即d可能恰好等于最大深度 1此时相当于在最深层叶子节点之下追加一层给定的二叉树至少包含一个节点无需处理空树输入。题目大意根节点为第 1 层深度为 1。在其第d层追加一行值为v的节点。规则如下给定深度值d正整数针对深度d-1层的每一个非空节点 N为 N 创建两个值为v的左子树和右子树。将 N 原先的左子树连接为新节点 v 的左子树将 N 原先的右子树连接为新节点 v 的右子树。如果d的值为 1深度d-1不存在则创建一个新的根节点 v原先的整棵树作为 v 的左子树。解题思路总体思路遍历到目标层的前一层再插入这一题虽然标为 Medium实际非常简单。给二叉树添加一行可以用 DFS 或 BFS在遍历过程中记录当前层数到达目标行的上一层即d-1层时为每个节点挂上两个新节点即可完成插入。遍历到d-1层后插入操作是 O(1) 的指针重连因此整体时间复杂度和遍历复杂度一致时间复杂度O(n)n 为树的节点数最坏情况下需要遍历整棵树空间复杂度O(n)DFS 递归时栈的深度最坏为树高退化链表时为 O(n)。边界情况一d 1替换根节点当d 1时d-1层不存在没有父节点可供挂载新行。此时创建一个新节点tmp : TreeNode{Val: v, Left: root, Right: nil}把原树整体作为新根的左子树直接返回新根即可。边界情况二d 超过树高在叶子之下追加一层原题保证d ≤ 最大深度 1因此当d等于最大深度 1时递归会一直向下走到最深层叶子节点。在叶子节点处判断*currLevel d-1成立此时root.Left和root.Right均为 nil为叶子节点挂上两个值为v的新叶子节点就等价于在最下层追加了一行。代码实现本题实现位于仓库 leetcode/0623.Add-One-Row-to-Tree/623. Add One Row to Tree.go完整代码如下package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func addOneRow(root *TreeNode, v int, d int) *TreeNode { if d 1 { tmp : TreeNode{Val: v, Left: root, Right: nil} return tmp } level : 1 addTreeRow(root, v, d, level) return root } func addTreeRow(root *TreeNode, v, d int, currLevel *int) { if *currLevel d-1 { root.Left TreeNode{Val: v, Left: root.Left, Right: nil} root.Right TreeNode{Val: v, Left: nil, Right: root.Right} return } *currLevel if root.Left ! nil { addTreeRow(root.Left, v, d, currLevel) } if root.Right ! nil { addTreeRow(root.Right, v, d, currLevel) } *currLevel-- }代码要点逐行拆解addOneRow是入口函数首先处理d 1的特例——新建根节点Left指向原rootRight为 nil直接返回否则初始化当前层数level : 1递归调用addTreeRow最终仍返回原来的root因为非d1时根节点不会被替换。addTreeRow是前序遍历的递归体用指针currLevel *int在整棵树的递归过程中共享当前层数这一状态当*currLevel d-1时说明当前节点位于目标行的上一层直接执行插入root.Left被替换为TreeNode{Val: v, Left: root.Left, Right: nil}——新节点接管原左子树root.Right被替换为TreeNode{Val: v, Left: nil, Right: root.Right}——新节点接管原右子树。插入后return不再向下递归。否则*currLevel进入下一层先递归左子树、再递归右子树递归返回后*currLevel--回溯到上一层保证兄弟分支的层数状态正确。之所以用*int指针而不是返回值传递层数是为了让左、右子树的递归共享同一个层数计数器并利用回溯/--恢复现场避免每层拷贝。数据结构依赖代码通过type TreeNode structures.TreeNode别名直接复用仓库 structures/TreeNode.go 中定义的标准二叉树节点type TreeNode struct { Val int Left *TreeNode Right *TreeNode }TreeNode定义在第 813 行这是 LeetCode-Go 全仓库共用的树节点结构测试与树构造工具如Ints2TreeNode、Tree2Preorder也全部复用该结构。测试用例与验证本题测试位于仓库 leetcode/0623.Add-One-Row-to-Tree/623. Add One Row to Tree_test.go采用仓库统一的para/ans表驱动测试风格输入树层序vd期望输出前序遍历覆盖场景[4,2,6,3,1,5,NULL]12[4,1,1,2,NULL,NULL,6,3,1,5,NULL]示例 1根节点下一层插入[4,2,NULL,3,1]13[4,2,NULL,1,1,3,NULL,NULL,1]示例 2单侧链上插入[1,2,3,4]54[1,2,3,4,NULL,NULL,NULL,5,5]d 树高 1最底层叶子之下追加一行[4,2,6,3,1,5]13[4,2,6,1,1,1,1,3,NULL,NULL,1,5]中间层插入原子树整体下移[4,2,6,3,1,5]11[1,4,NULL,2,6,3,1,5]d 1替换根节点测试用例的构造与断言依赖 structures 包的两个工具函数Ints2TreeNode按层序[]int数组生成二叉树其中用NULL -1 63定义于 structures/TreeNode.go表示空节点Tree2Preorder把插入结果二叉树转换回前序遍历切片便于断言比较。例如第三条用例[1,2,3,4]对应 d4、树高为 3 的情况验证了追加行高于原树高时新节点会正确地落在最深层叶子节点之下。第五条用例则完整验证了d 1时新根节点的创建与旧树整体左挂的行为。运行测试可直接在仓库根目录执行go test ./leetcode/0623.Add-One-Row-to-Tree/总结本题的核心模型是在树的某一行整体插入一层节点用 DFS 前序遍历并维护当前层数当层数到达d-1时执行 O(1) 的指针重连插入两个边界分支缺一不可d 1需要新建根节点并整体左挂原树d 树高 1需要在最深层叶子节点之下追加插入动作的本质是新节点接管旧子树——新左节点继承原左子树新右节点继承原右子树原有节点在树中的相对顺序完全不变因此只需一次遍历即可完成时间复杂度 O(n)、空间复杂度 O(n)。若希望练习 BFS层序遍历实现可以按同样的到达d-1层即插入思路用队列按层扫描在d-1层对每个节点执行相同的指针重连可作为对 DFS 解法之外的补充练习。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考