一、题目描述：
继续今日一题，进行二叉树的修炼
二叉树的题目，其实相对还比较好做，因为咱们掌握了一定套路
二、这道题考察了什么思想？你的思路是什么？
给一棵二叉树中的某一层添加数字，题目给定了我们一些规则，我们来翻译一下：
- 题目敲定树的 root 节点深度为 1,需要咱们在 depth 深度位置处添加一层节点值
- 对于添加到的 depth-1 层有节点时，那么咱们以 depth-1 层的节点为父节点，创建左节点和右节点，当前左节点的左子树是原有节点的左子树，现在右节点的右子树，是原有节点的右子树
- 当输入的 depth 等于 1 的时候，相当于，咱们当前是要创建一个根节点，且把原来的depth 为 1 的节点放到新节点的左边
分析
就这么来看，要是我们用积木来搭建的话，肯定很容易就能理解，甚至还可以玩出花来
做二叉树，用的最多的就是深度优先和广度优先来进行处理，一个使用递归，一个使用迭代，看我们乐意使用哪一种方式了
对于本题，我们可以使用深度优先的方式去进行遍历，并且我们可以将以整棵二叉树，看成一小颗一小颗的子二叉树，层级最高为 2
那么当我们需要增加的 depth 为 1 的时候，咱们就直接创建根节点即可，要是 depth 为 2，咱们就直接在根节点的上做文章
给根节点加上左子和右子，以前根节点的左子就是当前左子的左子，以前根节点的右子，就是当前右子的右子
例如这样，我们可以演示一下，例如示例 1
这个时候，我们知道，示例 1 的 depth 是 2，因此，我们都不用继续进行递归了，直接在树的第一层，也就是 depth -1 层，添加当前节点的左子和右子，然后按照逻辑调整指向即可
因此，当 depth 小于等于 2 的时候，其实我们都不需要递归，当 depth 大于 2 的时候，咱们就可以开始递归，并且可以将所有的问题，全部转成当 depth 等于 1 或者 depth 等于 2 来处理，只是处理时当前的根节点不一样而已
接下来就开始撸代码吧，我想咱们已经可以很明确的写出代码来了
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
- 咱们重点处理 depth 等于 1 和 depth 等于 2 即可
编码如下：
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func addOneRow(root *TreeNode, val int, depth int) *TreeNode { // 直接使用递归的方式 if root == nil { return nil } if depth == 1 { return &TreeNode{val, root, nil} } if depth == 2 { root.Left = &TreeNode{val, root.Left, nil} root.Right = &TreeNode{val, nil, root.Right} } else { root.Left = addOneRow(root.Left, val, depth-1) root.Right = addOneRow(root.Right, val, depth-1) } return root }
四、总结：
本次的这种实现方式直接是深度优先算法，直接递归，按照层级来处理 ，时间复杂度是 O(n) ，根据层级的不同，咱们遍历的深度也不同，最深的情况就是整棵树都会遍历到，则 空间复杂度也是 O(n)
原题地址：623. 在二叉树中增加一行
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
