623. Add One Row to Tree
给予一个二元树，我们要在高度为depth的位置插入一行数值为val的节点。
若depth为1，因为没有存在深度为0的树所以令root为新的节点的左树。
Example 1:
https://assets.leetcode.com/uploads/2021/03/15/addrow-tree.jpg
Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]
思路：
1.对树进行dfs并用一个boolean纪录上个节点是对左树还是右树访问
2.当深度为1的时候表示要在这层进行插入，new一个节点并根据上个访问的节点是
左树还右树来决定要把下一层放左还放右
Java Code：
class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
return addOneRow(root, val, depth, true);
}
public TreeNode addOneRow(TreeNode root, int val, int depth, boolean
isLeft) {
if(depth == 1) {
TreeNode node = new TreeNode(val);
if(isLeft) node.left = root;
else node.right = root;
return node;
}
if(root == null) return null;
root.left = addOneRow(root.left, val, depth - 1, true);
root.right = addOneRow(root.right, val, depth - 1, false);
return root;
}
}
今天也是温柔善良的树 好耶