mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-04 16:12:47 +08:00
110 lines
3.2 KiB
Markdown
110 lines
3.2 KiB
Markdown
# [623. Add One Row to Tree](https://leetcode.com/problems/add-one-row-to-tree/)
|
||
|
||
|
||
## 题目
|
||
|
||
Given the root of a binary tree, then value `v` and depth `d`, you need to add a row of nodes with value `v` at the given depth `d`. The root node is at depth 1.
|
||
|
||
The adding rule is: given a positive integer depth `d`, for each NOT null tree nodes `N` in depth `d-1`, create two tree nodes with value `v` as `N's` left subtree root and right subtree root. And `N's` **original left subtree** should be the left subtree of the new left subtree root, its **original right subtree** should be the right subtree of the new right subtree root. If depth `d` is 1 that means there is no depth d-1 at all, then create a tree node with value **v** as the new root of the whole original tree, and the original tree is the new root's left subtree.
|
||
|
||
**Example 1:**
|
||
|
||
```
|
||
Input:
|
||
A binary tree as following:
|
||
4
|
||
/ \
|
||
2 6
|
||
/ \ /
|
||
3 1 5
|
||
|
||
v = 1d = 2Output:
|
||
4
|
||
/ \
|
||
1 1
|
||
/ \
|
||
2 6
|
||
/ \ /
|
||
3 1 5
|
||
```
|
||
|
||
**Example 2:**
|
||
|
||
```
|
||
Input:
|
||
A binary tree as following:
|
||
4
|
||
/
|
||
2
|
||
/ \
|
||
3 1
|
||
|
||
v = 1d = 3Output:
|
||
4
|
||
/
|
||
2
|
||
/ \
|
||
1 1
|
||
/ \
|
||
3 1
|
||
```
|
||
|
||
**Note:**
|
||
|
||
1. The given d is in range [1, maximum depth of the given tree + 1].
|
||
2. The given binary tree has at least one tree node.
|
||
|
||
## 题目大意
|
||
|
||
给定一个二叉树，根节点为第1层，深度为 1。在其第 d 层追加一行值为 v 的节点。添加规则：给定一个深度值 d （正整数），针对深度为 d-1 层的每一非空节点 N，为 N 创建两个值为 v 的左子树和右子树。将 N 原先的左子树，连接为新节点 v 的左子树；将 N 原先的右子树，连接为新节点 v 的右子树。如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。
|
||
|
||
## 解题思路
|
||
|
||
- 这一题虽然是 Medium，实际非常简单。给二叉树添加一行，用 DFS 或者 BFS，遍历过程中记录行数，到达目标行一行，增加节点即可。不过需要注意 2 个特殊情况，特殊情况一，`d==1`，此时需要添加的行即为根节点。特殊情况二，`d>height(root)`，即要添加的行数比树还要高，这时只需要在最下层的叶子节点添加一层。时间复杂度 O(n)，空间复杂度 O(n)。
|
||
|
||
## 代码
|
||
|
||
```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--
|
||
}
|
||
``` |