标题链接：https://leetcode.cn/problems/add-one-row-to-tree/
标题形貌：
给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。
注意，根节点 root 位于深度 1 。
加法规则如下:
- 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
- cur 原来的左子树应该是新的左子树根的左子树。
- cur 原来的右子树应该是新的右子树根的右子树。
- 如果 depth == 1意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val作为整个原始树的新根，而原始树就是新根的左子树。
示例 1:
输入: root = [4,2,6,3,1,5], val = 1, depth = 2输出: [4,1,1,2,null,null,6,3,1,5]示例 2:
输入: root = [4,2,null,3,1], val = 1, depth = 3输出: [4,2,null,1,1,3,null,null,1]提示:
- 节点数在 [1, 104] 范围内
- 树的深度在 [1, 104]范围内
- -100 <= Node.val <= 100
- -105 <= val <= 105
- 1 <= depth <= the depth of tree + 1
解法：递归
刷了这么多二叉树的标题，总结下来，碰到二叉树标题，一多半都是递归解法。
递归算法的思绪：
（1）决定标题规模的参数。须要用递归算法办理的标题，其规模通常都是比力大的，在标题中决定规模巨细（或标题复杂程度）的量有哪些？把它们找出来。
（2）标题的界限条件及界限值。在什么环境下可以直接得出标题的解？这就是标题的界限条件及界限值。
（3）办理标题的通式。把规模大的、较难办理的标题变成规模较小、易办理的同一标题，须要通过哪些步调或等式来实现？这是办理递归标题的难点。把这些步调或等式确定下来。
分析：
根据标题形貌，我们可以找到三个界限条件：
（1）当树自己就为空时，那么效果肯定也为空
（2）当要插入的深度是1时，及新建根节点，将之前的根节点作为新结点的左子树。
（3）当要插入的深度是2时，及给根节点新建左右两个子节点，然后再分别将之前根节点的左子树作为新建的左节点的左子树，将之前根节点的右子树作为新建的右节点的右子树。
标题递归演变：
当要插入的深度depth大于2时，意味着，先要要找到depth-1的全部结点，再给这些结点分别创建左右结点，再将之前的左右子树作为新节点的子节点，雷同于上述第三个界限条件。
而树的遍历，可以使用递归算法，每遍历一次，根节点指向子节点，并让插入的深度减一，徐徐使标题走向界限，当深度为2时，就到达了之前的界限三的条件，退出递归。
代码： |
