简单理解为：在二叉树中的某一层，插入一行数据。
通常在二叉树的遍历中，最常用的就是递归和迭代，下面就从递归和迭代的两种思路来解题。
思路1：递归
首先定义一个计数器，记录每一次到达的层数，每次递归时进行自增。
开始进行递归。
如果到达了depth-1时，那么将这个节点与这个节点的子节点中间插入一层。
插入后直接返回，因为再往下递归没有意义。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
func addOneRow(root *TreeNode, val int, depth int) *TreeNode {
// 当depth为1时，只需要在root上面加一层就可以了，所以不必进入递归
if depth == 1{
return &TreeNode{
Val: val,
Left: root,
}
}
// 定义递归函数，root为遍历的节点，depth为计数器，当depth为2时，说明该节点的子节点就是目标层级。
var dfs func(root *TreeNode, depth int)
dfs = func(root *TreeNode, depth int) {
// 当root为空时，直接返回，说明该root不符合题意
if root == nil{
return
}
// 当depth>2时，说明还没有到达目标节点。
if depth > 2{
// 需要递归该节点的左右子节点，同时depth减1，表示进入了下一层。
dfs(root.Left, depth-1)
dfs(root.Right, depth-1)
return
}
// 如果depth等于2了，说明到达了目标节点，此时将该节点和两个子节点中间添加一层。
tmpLeft, tmpRight := root.Left, root.Right
root.Left = &TreeNode{
Val: val,
Left: tmpLeft,
}
root.Right = &TreeNode{
Val: val,
Right: tmpRight,
}
}
dfs(root, depth)
return root
}
|
思路2：迭代
首先定义一个切片，将root放进去，用来迭代。
定义一个层级的结果res，将迭代出来的层级数据存放在这个二位数组中，用于获取目标层级。
开始迭代。
迭代完成后，将目标层级的节点跟他们的左右子节点中添加一层后返回。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
func addOneRow(root *TreeNode, val int, depth int) *TreeNode {
// 当depth为1时，只需要在root上面加一层就可以了，所以不必进入递归
if depth == 1{
return &TreeNode{
Val: val,
Left: root,
}
}
// 定义用来存储即将用来迭代的切片，并将root节点放进去
var curr []*TreeNode
curr = append(curr, root)
// 定义迭代结果的切片res
var res [][]*TreeNode
// 开始迭代，直到curr内没有内容
for len(curr) > 0{
// 先将本层结果丢到切片中
res = append(res, curr)
// 定义临时切片用于存储下一层节点
var tmp []*TreeNode
// 将下一层节点都放入tmp中
for _, v := range curr{
if v.Left != nil{
tmp = append(tmp, v.Left)
}
if v.Right != nil{
tmp = append(tmp, v.Right)
}
}
// 将tmp放入curr，进行下一层的迭代
curr = tmp
}
// 如果res为空，说明该节点不符合题意
if len(res) == 0{
return nil
}
// 获取目标层的数据
tmp := res[depth-2]
// 遍历目标层的节点，将这些节点与左右子节点的中间添加一层
for _, v := range tmp{
tmpl, tmpr := v.Left, v.Right
v.Left = &TreeNode{
Val: val,
Left: tmpl,
}
v.Right = &TreeNode{
Val: val,
Right: tmpr,
}
}
return root
}
|
CloudNativeQingFeng
