题目名称

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

注意，根节点 root 位于深度 1 。

加法规则如下:

给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
cur 原来的左子树应该是新的左子树根的左子树。
cur 原来的右子树应该是新的右子树根的右子树。
如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。

示例

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

输出: [4,1,1,2,null,null,6,3,1,5]

题解

这道题主要还是考察二叉树的遍历，首先根据二叉树的层级遍历出一个二维数组（或者只要遍历到depth 所需要的深度即可，无需完全遍历），二维数组中的元素对应着每一层的节点及节点数

depth 实际上是获取 depth - 1 层的节点数，然后在根据获取到的节点及节点的左右子节点来添加新的左右子节点以及旧左右子节点的位置

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var addOneRow = function(root, val, depth) {
    let rootRow = flatRoot([[root]])
    if(depth === 1) {
        let r = { val: val, left: root, right: null}
        return r
    }
    let row = rootRow[depth - 2]
    for(let i = 0; i < row.length; i++) {
        let item = row[i]
        let { left, right } = item
        let l = { val, left: null, right: null}, r = { val, left: null, right: null }
        if(left && right) {
            l.left = left
            r.right = right
        } else if(left && !right) {
            l.left = left
        } else if(!left && right) {
            r.right = right
        }
        item.left = l
        item.right = r
    }
    return root
};

var flatRoot = (arr) => {
    let root = arr[arr.length - 1], newArr = []
    for(let i = 0; i < root.length; i++) {
        let item = root[i] 
        item.left && newArr.push(item.left) 
        item.right && newArr.push(item.right) 
    }
    if(newArr.length === 0) return arr
    arr.push(newArr)
    return flatRoot(arr)
}