1.题目

给定一个二叉树的根 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, 10⁴] 范围内
树的深度在 [1, 10⁴]范围内
-100 <= Node.val <= 100
-10⁵ <= val <= 10⁵
1 <= depth <= the depth of tree + 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/add-one-row-to-tree

2.思路

（1）BFS
每遍历每一层时，用变量 curDepth 来记录当前深度，当 curDepth == depth - 1 时，说明下一层为要添加节点的层，此时便进行添加操作。

（2）DFS
同理，使用 DFS 时用变量 curDepth 来记录当前深度，到达第 depth - 1 层时，进行添加操作。

3.代码实现（Java）

//思路1————BFS
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            return new TreeNode(val, root, null);
        }
        //BFS
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.addLast(root);
        int curDepth = 1;
        while (!deque.isEmpty()) {
            // levelSize 记录当前层的节点数量
            int levelSize = deque.size();
            while (levelSize > 0) {
                //取出队首节点
                TreeNode curNode = deque.poll();
                if (curDepth == depth - 1) {
                    //下一层为要添加节点的层
                    TreeNode node1 = new TreeNode(val);
                    TreeNode node2 = new TreeNode(val);
                    node1.left = curNode.left;
                    node2.right = curNode.right;
                    curNode.left = node1;
                    curNode.right = node2;
                } else {
                    if (curNode.left != null) {
                        deque.addLast(curNode.left);
                    }
                    if (curNode.right != null) {
                        deque.addLast(curNode.right);
                    }
                }
                levelSize--;
            }
            curDepth++;
        }
        return root;
    }
}

//思路2————DFS
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            return new TreeNode(val, root, null);
        }
        dfs(root, 1, val, depth);
        return root;
    }

    public void dfs(TreeNode root, int curDepth, int val, int depth) {
        if (root == null) {
            return;
        }
        if (curDepth == 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, curDepth + 1, val, depth);
            dfs(root.right, curDepth + 1, val, depth);
        }
    }
}