curr variable has a reference to root on the first iteration of while loop, but starting from second iteration curr variable should have a reference to a newly created node every iteration?
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);
<iframe name="sif1" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>
CodePudding user response:
The root
variable just references the root object. That doesn't change during the process of extension. But during that process, the left
and right
properties of that object change value (from null
to a new node).
In the first iteration of the loop, curr
gets to reference the same object as root
, and so whatever mutation is brought to curr
is brought to root
: both variables are giving access to the same single object. As the code sets curr.left
to a new node and sets curr.right
to a new node, at that moment root.left
and root.right
have been set to new nodes.
In the next iteration, curr
will reference one of those newly created nodes (which are already "attached" to root
), and the same happens there: as curr
is mutated, we actually mutate a node that can be reached from root
. That deeper node gets extended with new nodes referenced by its left
and/or right
properties.
CodePudding user response:
I think trincot answered your question. If that isn't clear, please comment.
But if you want a version of this that involves no mutation, you can do it recursively, by noting that the left child of the node formed from the value at index i
is the one formed from the value at index 2 * i 1
and the right child from the value at index 2 * i 2
, assuming they exist:
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}
<iframe name="sif2" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>
This does not use your TreeNode constructor. Unless there's more to it than is shown, I see no reason for it. But if we need to use it, we could replace this:
: {value: xs [i], left: toTree (xs, 2 * i 1), right: toTree (xs, 2 * i 2)}
with this:
: new TreeNode (xs [i], toTree (xs, 2 * i 1), toTree (xs, 2 * i 2))