加一行！
今天看到一道有趣的题目，分享给大家。
题目不难，但是我感觉挺有意思，大家可以看一下。
做该题之前，我们先来复习下二叉树的基础知识，重点关注节点的层数和深度之间的关系。
更多基础知识大家可以看这篇文章，一文读懂二叉树。
话不多说，咱们直接看题。
leetcode 623在二叉树中增加一行
题目很容易理解，让我们在二叉树特定的层数添加一层特定的节点。见下图
有点丑见谅
大家有没有发现添加前和添加后，有什么不同？是不是多了一层节点，然后还变丑了？尽力了哈哈，还是画的不帅。
题目已经搞懂，那么大家看到这个题目的第一想法是什么呢？
我的想法是直接进行层序遍历，然后找到对应的层，直接添加新节点即可，和向链表中添加节点的含义类似。
大家如果忘记了层序遍历，可以去这个文章进行复习，这里对可以使用层序遍历的题目进行了总结。
好啦既然我们已经有了做题思路，那么咱们直接直接将思路模拟出来吧！
我们使用这棵树来举例
向这棵树的第 3 层插入，值为 0 的节点。
上面的动画中，为了表述清晰，所以将添加节点的步骤进行了省略，直接进行添加，具体步骤如下。
插入新节点步骤
好啦，到这里我们这个题目就解决啦，下面我们直接看代码吧，当然我这里只是一种写法，大家可以随意发挥。
BFS代码
class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
int level = 0;
Queue<TreeNode> queue = new LinkedList<>();
if (depth == 1) {
TreeNode test = new TreeNode(val);
test.left = root;
return test;
}
queue.add(root);
while (!queue.isEmpty()) {
level++;
int size = queue.size();
for (int i = 0 ; i < size; ++i) {
TreeNode temp = queue.poll();
if (level == depth - 1) {
TreeNode node1 = new TreeNode(val);
TreeNode node2 = new TreeNode(val);
node1.left = temp.left;
node2.right = temp.right;
temp.left = node1;
temp.right = node2;
} else {
if (temp.left != null) queue.offer(temp.left);
if (temp.right != null) queue.offer(temp.right);
}
}
if (depth - 1 == level) break;
}
return root;
}
}
时间复杂度O（n）空间复杂度O（n）
当然这个题目也可以使用 dfs 解决，具体思路如下。是个很简单的深度优先搜索，当达到指定层数的某节点时，为其添加节点即可。
那我们来想一下结束递归的条件，当root == null 时，我们直接 return；当我们搜索到待插入的那一层时，我们直接插入节点即可，否则的则继续进行搜索，代码很简单，比仅仅比二叉树的 dfs 多了一丢丢逻辑。
其实你搞定上面的那个方法，这个也很快就能想到嘞，那么我们直接看代码吧。
DFS代码
class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
if (depth == 1) {
TreeNode temp = new TreeNode(val);
temp.left = root;
return temp;
}
dfs(root,val,depth,1);
return root;
}
public void dfs(TreeNode root, int val, int depth, int level) {
if (root == null) {
return;
}
if (level == depth - 1) {
TreeNode node1 = new TreeNode(val);
TreeNode node2 = new TreeNode(val);
node1.left = root.left;
node2.right = root.right;
root.left = node1;
root.right = node2;
} else {
dfs(root.left, val, depth, level+1);
dfs(root.right, val, depth, level+1);
}
}
}
时间复杂度O（n）,空间复杂度O（n）。
好啦，今天就唠到这吧，有需要进入刷题小队的同学，可以小屋内点击刷题小队进入，拜了个拜。