题目描述

给定一个二叉树的root和两个整数val和depth，在给定的深度depth处添加一个值val的节点行。注意，根节点root位于深度1.

示例1:

输入：root=[4,2,6,3], val=1, depth=1

输出：[1,4,null,2,6,3]

解题思路

使用层序遍历，来解决这个问题；这里会使用到队列，层序遍历实现思路如下：

1. 先把root写入到队列中；
2. 如果队列不为空，则继续执行，否则跳出循环。
3. 循环体中，从队列中取出数据，并且如果有左子树则把左子树加入队列，如果有右子树则把右子树加入队列。

接着考虑，在给定的深度depth处添加一个值val的节点行。

1. 如何获取深度，每次遍历完成一次，则把深度加1；
2. 找到指定的深度后，只需要添加左子树或者右子树，就完成代码了。

代码实现

 
import org.example.TreeNode;
 
import java.util.Deque;
import java.util.LinkedList;
 
class Solution1 {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
 
        if (depth == 1) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
 
        TreeNode root0 = root;
        Deque deque = new LinkedList<>();
        if (root != null) {
            deque.offer(root);
        }
 
        int count = 0;
        while (!deque.isEmpty()) {
            count++;
            int sz = deque.size();
            for (int i = 0; i < sz; i++) {
                TreeNode node = deque.poll();
                if (count == depth - 1) {
                    TreeNode left = node.left;
                    TreeNode right = node.right;
 
                    node.left = new TreeNode(val);
                    node.left.left = left;
 
                    node.right = new TreeNode(val);
                    node.right.right = right;
 
                } else {
                    if (node.left != null) {
                        deque.offer(node.left);
                    }
                    if (node.right != null) {
                        deque.offer(node.right);
                    }
                }
            }
 
        }
        return root0;
    }
}

总结

这道题比较复杂的点是理解题目，什么时候需要添加新节点，层序遍历属于标准流程。

这里使用时我遇到一个耗时优化点，就是使用队列时到底用哪种实现，最开始我使用ArrayDeque发现耗时还是挺高的，主要原因是在offer和poll操作影响耗时。后来切换成LinkedList后，发现耗时就降低下来了，原因是在offer和poll操作时，只需要移动当前元素，更加适合这种频繁变更的场景。