打印二叉树递归函数

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(''));因为您用相同的数组填充了数组。带下划线的部分用相同的数组填充，为常数。