打印二叉树递归函数

Question

我试图返回代表二叉树的数组的数组。我创建了一个输出数组，其中填充了空字符串数组，其中每个数组代表树的一个级别，字符串代表该级别上每个可能的节点位置。出于某种原因，看来我的递归函数正在更改父输出数组中的所有数组，而不仅仅是适当的数组。var printTree = function(root) {//first find depth of tree    let depth = 0    const findDepth = (node, level) => {        depth = Math.max(depth, level);        if (node.left) {            findDepth(node.left, level + 1)        }        if (node.right) {            findDepth(node.right, level + 1)        }    }    findDepth(root, 1);    let width = 1 + ((depth - 1) * 2)//create array of arrays filled with blanks that match height and width// of given tree    let output = new Array(depth).fill(new Array(width).fill(''));    let mid = Math.floor(width / 2);//do DFS through tree and change output array based on position in tree    const populate = (node, level, hori) => {        output[level][hori] = node.val;        if (node.left) {            populate(node.left, level + 1, hori - 1);        }        if (node.right) {            populate(node.right, level + 1, hori + 1);        }    }    populate(root, 0, mid);    return output;};如果我将二叉树的根节点的val设置为1，则其唯一的子节点的val设置为2。我的输出数组应该是：[['', 1 , ''],[2 , '' , '']]但是相反，它看起来像这样：[[2, 1, ''],[2, 1, '']]我已经在控制台上记录了递归调用，但我无法弄清楚为什么这些变化是在矩阵的所有行中进行的，而不仅仅是在适当的级别上进行的。我该如何解决这个问题？

Answer 1

您需要更改此行

let output = new Array(depth).fill(new Array(width).fill(''));

//                                 ^^^^^^^^^^^^^^^^^^^^^^^^^ same array!

进入

let output = Array.from({ length: depth }, _ => Array.from({ length: width }).fill(''));

因为您用相同的数组填充了数组。带下划线的部分用相同的数组填充，为常数。