为什么 root 变量最终保留了 while 循环内生成的整棵树的结果？

Question

curr 变量在 while 循环的第一次迭代中引用了 root，但是从第二次迭代开始，curr 变量应该在每次迭代中引用一个新创建的节点？[=11=]

var TreeNode = function (value, left, right) {
    this.value = value;
    this.left = left;
    this.right = right;
};

function arrayToTree(array) {
    if (!array.length) return undefined;
    var root = new TreeNode(array.shift());
    var queue = [root];

    while (array.length) {
        var curr = queue.shift();
        var left = new TreeNode(array.shift());
        curr.left = left;
        queue.push(left);
        if (!array.length) break;
        var right = new TreeNode(array.shift());
        queue.push(right);
        curr.right = right;
    }

    return root;
};

const ret = arrayToTree([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

console.log(ret);

Answer 1

root 变量仅引用根对象。这在扩展过程中不会改变。但在该过程中，该对象的 left 和 right 属性更改值（从 null 到新节点）。

在循环的第一次迭代中，curr 引用了与 root 相同的对象，因此 curr 的任何变化都会被带到 root：两个变量都允许访问 same 单个对象。由于代码将 curr.left 设置为新节点并将 curr.right 设置为新节点，此时 root.left 和 root.right 已设置为新节点。

在下一次迭代中，curr 将引用其中一个新创建的节点（已经“附加”到 root），同样的情况也会发生：如 curr被变异，我们实际上变异了一个可以从root到达的节点。该更深的节点通过其 left and/or right 属性引用的新节点进行扩展。

Answer 2

我想 trincot 回答了你的问题。如果不清楚，请发表评论。

但是如果你想要一个不涉及突变的版本，你可以递归地完成它，注意由索引 i 处的值形成的节点的左侧 child 是一个由索引 2 * i + 1 处的值形成，右侧 child 由索引 2 * i + 2 处的值形成，假设它们存在：

const toTree = (xs, i = 0) =>
  i >= xs .length
    ? undefined
    : {value: xs [i], left: toTree (xs, 2 * i + 1), right: toTree (xs, 2 * i + 2)}

console .log (toTree ([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]))

.as-console-wrapper {max-height: 100% !important; top: 0}

这不使用您的 TreeNode 构造函数。除非它比显示的更多，否则我认为没有理由这样做。但是如果我们需要使用它，我们可以替换这个：

    : {value: xs [i], left: toTree (xs, 2 * i + 1), right: toTree (xs, 2 * i + 2)}

有了这个：

    : new TreeNode (xs [i], toTree (xs, 2 * i + 1), toTree (xs, 2 * i + 2))

为什么 root 变量最终保留了 while 循环内生成的整棵树的结果？

Why does the root variable eventually keep the result of the whole tree which is made inside the while loop?

javascript

algorithm

tree