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;
}
}
今天也是溫柔善良的樹 好耶