JavaScript 从数组构建不完整的二叉树
JavaScript build Incomplete Binary Tree from an array
这似乎是一个重复的问题，但我无法在 SOF 或其他地方的任何地方找到我的问题的答案。
我想从一个数组和一个非空根节点不完整的二叉树 =63=]，在 JavaScript 中，值为 null 表示 null 子树，而不是值为 null 的子树。
预期结果：
TreeNode {
val: 1,
left:
TreeNode {
val: 2,
left: TreeNode { val: 4, left: null, right: null },
right: null },
right:
TreeNode {
val: 3,
left: null,
right: TreeNode { val: 5, left: null, right: null } } }
上面的预期输出可以像这样手动完成：
const myTree = new TreeNode(1);
myTree.left = new TreeNode(2);
myTree.left.left = new TreeNode(4);
myTree.right = new TreeNode(3);
myTree.right.right = new TreeNode(5);
树应该是这样的：
1
/\
2 3
/ \
4 5
这是我的代码：
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
insert(values, i = 0) {
if (i >= values.length) return;
const queue = [this];
while (queue.length > 0) {
let current = queue.shift();
if (current.left === null) {
current.left = new TreeNode(values[i]);
break;
}
queue.push(current.left);
if (current.right === null) {
current.right = new TreeNode(values[i]);
break;
}
queue.push(current.right);
}
this.insert(values, i + 1);
return this;
}
}
(function() {
// This builds a tree with null nodes with null values and null children.
// The goal is to skip updating any null child
const myTree = new TreeNode(1);
myTree.insert2([2,3,4,null,null,5]);
console.log(myTree);
}());
这里的问题是我得到了一个 null 子节点作为 TreeNode，其值为 null，如下所示：
TreeNode {
value: 1,
left:
TreeNode {
value: 2,
left: TreeNode { value: 4, left: null, right: null },
right: TreeNode { value: null, left: null, right: null } },
right:
TreeNode {
value: 3,
left: TreeNode { value: null, left: null, right: null },
right: TreeNode { value: 5, left: null, right: null } } }
我可以通过添加以下内容来处理空节点的子节点：
constructor(value) {
this.value = value;
if (value) this.left = null;
if (value) this.right = null;
}
但我无法仅添加 null 值而不是完整的 TreeNode。
我试过：
if (current.left === null) {
current.left = values[i] !== null ? new BinaryTree(values[i]) : null;
break;
}
或：
if (current.left === null && values[i]) {}
或：
if (!values[i]) return;
但是nonereturns预期的结果。
我也看过一些使用 Java 的解决方案，但答案使用 Java 中的内置 LinkedList，所以我不确定这是在 JS 中做的正确方法。
Answer to Scott Sauyet's question:
的预期结果
const myTree = new TreeNode (1);
myTree .insert ([2,null, 4, null, 6, 7])
是：
TreeNode {
val: 1,
left: TreeNode {
val: 2,
left: TreeNode {
val: 4,
left: TreeNode { val: 6, left: null, right: null },
right: TreeNode { val: 7, left: null, right: null }
},
right: null
},
right: null
}
您通过为 null 检查 values[i] 并且在 null 时不创建新节点而做对了，但是您还需要跳过该节点以获取任何后续值。这在递归解决方案中很难做到，所以我建议让它迭代：
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
insert(values) {
const queue = [this];
let i = 0;
while (queue.length > 0) {
let current = queue.shift();
for (let side of ["left", "right"]) {
if (!current[side]) {
if (values[i] !== null) {
current[side] = new TreeNode(values[i]);
}
i++;
if (i >= values.length) return this;
}
if (current[side]) queue.push(current[side]);
}
}
return this;
}
}
(function() {
const myTree = new TreeNode(1);
myTree.insert([2,3,4,null,null,5]);
console.log(myTree);
}());
请注意，如果您多次调用 myTree.insert，那么之前的 null 个节点 将 扩展为新数据。
如果不需要，那么您可以采取的一种措施是删除 insert 方法，并仅通过构造函数提供此功能。
或者，否则，首先需要使用排队机制找出哪些是应该扩展的节点。它们是那些没有 2 children，并且没有跟随（按 BFS 顺序）具有 children.
的节点
这是它的外观（使用稍大一点的树作为演示）：
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
getInsertionPoints() {
// find uninterrupted series of leaves in BFS order
const queue = [this];
const leaves = [];
while (queue.length) {
let current = queue.shift();
for (let side of ["left", "right"]) {
if (current[side]) {
queue.push(current[side]);
leaves.length = 0; // reset
} else {
leaves.push([current, side]);
}
}
}
return leaves;
}
insert(values) {
let queue = this.getInsertionPoints();
for (let value of values) {
let [current, side] = queue.shift();
if (value !== null) {
current[side] = new TreeNode(value);
queue.push([current[side], "left"], [current[side], "right"]);
}
}
return this;
}
}
(function() {
const myTree = new TreeNode(1);
myTree .insert ([2,null, 4, null, 6, 7]);
myTree .insert ([8, null, 9, 10, 11, 12]);
console.log(myTree);
}());
这是一种不同的方法，通过计算节点的目标。
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
insert(values) {
let size = 1,
number = 0;
for (let value of values) {
if (value !== null) {
[...(number.toString(2).padStart(size, 0))].reduce((node, index, i, { length }) => {
let side = ['left', 'right'][index];
if (node[side] === null) {
node[side] = new TreeNode(i + 1 === length ? value : 'missing');
}
return node[side];
}, this);
}
number++;
if (number === 1 << size) {
size++;
number = 0;
}
}
}
}
const myTree = new TreeNode(1);
myTree.insert([2, 3, 4, null, null, 5]);
console.log(myTree);
.as-console-wrapper { max-height: 100% !important; top: 0; }
基于@trincot 的迭代解决方案，下面的代码在输入上循环，而不是在队列上循环。
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
insert(values) {
// clear current children before insert
this.left = this.right = null;
const queue = [this];
for (var i = 0; i < values.length; ) {
const current = queue.shift();
for (let side of ["left", "right"]) {
if (i < values.length && values[i] !== null) {
current[side] = new TreeNode(values[i]);
queue.push(current[side]);
}
++i;
}
}
return this;
}
}
const myTree = new TreeNode(1);
myTree.insert([2,3,4,null,null,5]);
console.log(myTree);
请注意，您将始终从左到右填充节点，并且每个级别都沿着树级别向下（根据您的要求跳过空值）。更深的节点总是新创建的，每个节点只被访问一次。因此，无需检查之前是否设置了 left 或 right 子项。
添加了额外的检查 i < values.length，因为输入数组可能包含奇数个条目（缺少树的最右边的底部元素）。
我会重新设计 insert 函数，以便它在子实例而不是父实例上递归调用 insert。
如果示例数组包含 15 个元素，则它的值位于索引 0-14 处。我们在索引和树中位置之间有一个映射。以下是索引如何映射到具有 15 个节点的完整树：
0
/ \
/ \
/ \
/ \
/ \
1 2
/ \ / \
/ \ / \
3 4 5 6
/ \ / \ / \ / \
7 8 9 10 11 12 13 14
当我们将根节点 #0 告诉 .insert([ 'a', 'b', 'c', 'd', 'e', 'f', ... ]) 时，我们知道节点 #1 获取索引 0 处的值 ('a')，#2 获取索引 1 处的值 ( 'b')，等等。节点 #1 获取索引 0，节点 #2 获取索引 1，节点 #3 获取索引 2...模式是索引 n 是节点 #[= 的值20=]。这是因为索引 0 不是指根节点而是根节点的左子节点。
父节点的索引与其子节点的索引之间存在关系。我们可以称之为 getChildIndices(parIndex):
getChildIndices(0) = [ 1, 2 ];
getChildIndices(1) = [ 3, 4 ];
getChildIndices(2) = [ 5, 6 ];
getChildIndices(3) = [ 7, 8 ];
getChildIndices(4) = [ 9, 10 ];
getChildIndices(5) = [ 11, 12 ];
getChildIndices(6) = [ 13, 14 ];
.
.
.
由于您选择的这个映射具有一定的优雅性，所以功能非常简单：
let getChildIndices = parIndex => [ parIndex * 2 + 1, parIndex * 2 + 2 ];
这样我们就可以写出更优雅的插入函数了：
let getChildIndices = parInd => [ parInd * 2 + 1, parInd * 2 + 2 ];
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
insert(values, myInd=0) {
let [ lInd, rInd ] = getChildIndices(myInd);
let vals = [
{ ind: lInd, prop: 'left' }, // `lInd` corresponds to our "left" property
{ ind: rInd, prop: 'right'} // `rInd` corresponds to our "right" property
];
for (let { ind, prop } of vals) {
// If we're out-of-bounds in `values`, stop!
if ((ind - 1) >= values.length) continue;
// A value of `null` in `values` indicates the subtree is null. Otherwise, a child
// node exists.
let shouldNodeExist = values[ind - 1] !== null;
if (this[prop] && !shouldNodeExist) { // If the node exists and shouldn't...
// Set the node to null
this[prop] = null;
} else if (!this[prop] && shouldNodeExist) { // If the node doesn't exist and should...
// Create a new child node
this[prop] = new TreeNode(null);
}
// Recursively call insert on the new child node, informing it of its index
if (this[prop]) {
this[prop].value = values[ind - 1];
this[prop].insert(values, ind);
}
}
}
}
let tree1 = new TreeNode(1);
tree1.insert([ 2, 3, 4, null, null, 5 ]);
console.log({ tree1 });
let tree2 = new TreeNode(1);
tree2.insert([ 2, null, 4, null, 6, 7 ]);
console.log({ tree2 });
请注意，此 insert 方法允许从树中添加、修改和删除节点。任何包含 null 的索引都会导致其对应的子树被删除。
请注意，如果我们尝试使用此方法指定不连续的子树 - 例如我们在索引 3 和 4 处指定值，但 null 在其父索引 (1) 处，索引 1 处的整个子树将为空，索引 3 和 4 将被忽略。
更新
这可以通过专用的广度优先遍历函数变得更加清晰 (bft。)
const bft = (nodes) =>
nodes .length == 0
? []
: [
...nodes,
...bft(nodes.flatMap (n => n .left ? n.right ? [n.left, n.right] : [n.left] : []))
]
class TreeNode {
constructor (val) {
this.val = val
}
insert (vals) {
return vals.reduce ((
tree, val, _, __,
parent = bft([tree]) .find (n => n.left === void 0 || n.right === void 0) || {}
) =>
((parent [parent.left === void 0 ? 'left' : 'right'] = val === null
? null
: new TreeNode(val)),
tree),
this)
}
}
你可以在下面的片段中看到这种方法：
const bft = (nodes) =>
nodes .length == 0
? []
: [
...nodes,
...bft(nodes.flatMap (n => n .left ? n.right ? [n.left, n.right] : [n.left] : []))
]
class TreeNode {
constructor (val) {
this.val = val
}
insert (vals) {
return vals.reduce ((
tree, val, _, __,
parent = bft([tree]) .find (n => n.left === void 0 || n.right === void 0) || {}
) =>
((parent [parent.left === void 0 ? 'left' : 'right'] = val === null
? null
: new TreeNode(val)),
tree),
this)
}
}
let myTree = new TreeNode (1);
myTree .insert ([2, 3, 4, null, null, 5]);
console .log (myTree);
// Handles subsequent inserts
myTree .insert ([6, null, null, null, 7, 8]);
console .log (myTree);
// Handles blocked nodes
myTree = new TreeNode(1);
myTree.insert([ 2, null, 4, null, 6, 7 ]);
console.log(myTree);
// Fails (somewhat) gracefully when node cannot be inserted
myTree = new TreeNode (1);
myTree .insert ([null, null, null, 2]);
console .log (myTree);
.as-console-wrapper {min-height: 100% !important; top: 0}
原答案
另一种可能性与此处的大多数答案不同。
大多数其他答案只允许一个 insert，此时它也可以折叠到构造函数中。
这个允许多个 inserts。但它不会将 left 和 right 子级设置为 null 除非我们在要插入的值中实际包含 null 。所以一些节点只有一个val，一些节点有一个val和left，而其他节点有一个val，一个left和一个right.通过留下这些洞，我们保留了以后添加其他节点的位置。
这种技术也相当优雅地处理了一切都已满的情况，只是拒绝添加剩余的节点。
class TreeNode {
constructor (val) {
this .val = val
}
insert (vals) {
return vals .reduce ((t, v) => {
const queue = [t]
while (queue .length) {
let node = queue .shift ()
if (node .left === void 0) {
node .left = v === null ? null : new TreeNode(v)
return t
} else if (node .right === void 0) {
node .right = v === null ? null : new TreeNode(v)
return t
} else {
if (node .left !== null) {
queue .push (node .left)
}
if (node .right !== null) {
queue.push (node.right)
}
}
}
return t // If we hit this point, then our insert failed: there's no room left.
}, this)
}
}
let myTree = new TreeNode (1);
myTree .insert ([2, 3, 4, null, null, 5]);
console .log (myTree);
// Handles subsequent inserts
myTree .insert ([6, null, null, null, 7, 8]);
console .log (myTree);
// Handles blocked nodes
myTree = new TreeNode(1);
myTree.insert([ 2, null, 4, null, 6, 7 ]);
console.log(myTree);
// Fails (somewhat) gracefully when node cannot be inserted
myTree = new TreeNode (1);
myTree .insert ([null, null, null, 2]);
console .log (myTree);
.as-console-wrapper {min-height: 100% !important; top: 0}
我们使用队列的广度优先遍历来保持节点仍然要访问，从根开始，如果我们还没有找到我们的插入点，则添加每个非空的左右子节点。
这样做的最大潜在缺点是不能保证任何节点的 left 或 right 子节点确实被定义。我们在这里使用 JS 的两个不同的 nil 值用于不同的目的。 null 表示该子树被阻塞。 undefined 表示虽然它尚不存在，但可以插入。有些人真的不喜欢以这种方式区分这两个 nilary 值。我认为它适用于语言的粒度，但是 YMMV。
这不是我特别引以为豪的代码。我更喜欢从不改变数据结构，而是总是创建新的数据结构。而且我更喜欢尽可能多地使用表达式而不是语句。但是我已经在这上面花了太长时间了，所以我现在不会花时间看看是否可以清理它。如果没有别的，它提供了一种与此处其他答案不同的方法，并解决了他们没有解决的某些问题。
这似乎是一个重复的问题，但我无法在 SOF 或其他地方的任何地方找到我的问题的答案。
我想从一个数组和一个非空根节点不完整的二叉树 =63=]，在 JavaScript 中，值为 null 表示 null 子树，而不是值为 null 的子树。
预期结果：
TreeNode {
val: 1,
left:
TreeNode {
val: 2,
left: TreeNode { val: 4, left: null, right: null },
right: null },
right:
TreeNode {
val: 3,
left: null,
right: TreeNode { val: 5, left: null, right: null } } }
上面的预期输出可以像这样手动完成：
const myTree = new TreeNode(1);
myTree.left = new TreeNode(2);
myTree.left.left = new TreeNode(4);
myTree.right = new TreeNode(3);
myTree.right.right = new TreeNode(5);
树应该是这样的：
1
/\
2 3
/ \
4 5
这是我的代码：
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
insert(values, i = 0) {
if (i >= values.length) return;
const queue = [this];
while (queue.length > 0) {
let current = queue.shift();
if (current.left === null) {
current.left = new TreeNode(values[i]);
break;
}
queue.push(current.left);
if (current.right === null) {
current.right = new TreeNode(values[i]);
break;
}
queue.push(current.right);
}
this.insert(values, i + 1);
return this;
}
}
(function() {
// This builds a tree with null nodes with null values and null children.
// The goal is to skip updating any null child
const myTree = new TreeNode(1);
myTree.insert2([2,3,4,null,null,5]);
console.log(myTree);
}());
这里的问题是我得到了一个 null 子节点作为 TreeNode，其值为 null，如下所示：
TreeNode {
value: 1,
left:
TreeNode {
value: 2,
left: TreeNode { value: 4, left: null, right: null },
right: TreeNode { value: null, left: null, right: null } },
right:
TreeNode {
value: 3,
left: TreeNode { value: null, left: null, right: null },
right: TreeNode { value: 5, left: null, right: null } } }
我可以通过添加以下内容来处理空节点的子节点：
constructor(value) {
this.value = value;
if (value) this.left = null;
if (value) this.right = null;
}
但我无法仅添加 null 值而不是完整的 TreeNode。
我试过：
if (current.left === null) {
current.left = values[i] !== null ? new BinaryTree(values[i]) : null;
break;
}
或：
if (current.left === null && values[i]) {}
或：
if (!values[i]) return;
但是nonereturns预期的结果。
我也看过一些使用 Java 的解决方案，但答案使用 Java 中的内置 LinkedList，所以我不确定这是在 JS 中做的正确方法。
的预期结果Answer to Scott Sauyet's question:
const myTree = new TreeNode (1);
myTree .insert ([2,null, 4, null, 6, 7])
是：
TreeNode {
val: 1,
left: TreeNode {
val: 2,
left: TreeNode {
val: 4,
left: TreeNode { val: 6, left: null, right: null },
right: TreeNode { val: 7, left: null, right: null }
},
right: null
},
right: null
}
您通过为 null 检查 values[i] 并且在 null 时不创建新节点而做对了，但是您还需要跳过该节点以获取任何后续值。这在递归解决方案中很难做到，所以我建议让它迭代：
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
insert(values) {
const queue = [this];
let i = 0;
while (queue.length > 0) {
let current = queue.shift();
for (let side of ["left", "right"]) {
if (!current[side]) {
if (values[i] !== null) {
current[side] = new TreeNode(values[i]);
}
i++;
if (i >= values.length) return this;
}
if (current[side]) queue.push(current[side]);
}
}
return this;
}
}
(function() {
const myTree = new TreeNode(1);
myTree.insert([2,3,4,null,null,5]);
console.log(myTree);
}());
请注意，如果您多次调用 myTree.insert，那么之前的 null 个节点 将 扩展为新数据。
如果不需要，那么您可以采取的一种措施是删除 insert 方法，并仅通过构造函数提供此功能。
或者，否则，首先需要使用排队机制找出哪些是应该扩展的节点。它们是那些没有 2 children，并且没有跟随（按 BFS 顺序）具有 children.
的节点这是它的外观（使用稍大一点的树作为演示）：
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
getInsertionPoints() {
// find uninterrupted series of leaves in BFS order
const queue = [this];
const leaves = [];
while (queue.length) {
let current = queue.shift();
for (let side of ["left", "right"]) {
if (current[side]) {
queue.push(current[side]);
leaves.length = 0; // reset
} else {
leaves.push([current, side]);
}
}
}
return leaves;
}
insert(values) {
let queue = this.getInsertionPoints();
for (let value of values) {
let [current, side] = queue.shift();
if (value !== null) {
current[side] = new TreeNode(value);
queue.push([current[side], "left"], [current[side], "right"]);
}
}
return this;
}
}
(function() {
const myTree = new TreeNode(1);
myTree .insert ([2,null, 4, null, 6, 7]);
myTree .insert ([8, null, 9, 10, 11, 12]);
console.log(myTree);
}());
这是一种不同的方法，通过计算节点的目标。
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
insert(values) {
let size = 1,
number = 0;
for (let value of values) {
if (value !== null) {
[...(number.toString(2).padStart(size, 0))].reduce((node, index, i, { length }) => {
let side = ['left', 'right'][index];
if (node[side] === null) {
node[side] = new TreeNode(i + 1 === length ? value : 'missing');
}
return node[side];
}, this);
}
number++;
if (number === 1 << size) {
size++;
number = 0;
}
}
}
}
const myTree = new TreeNode(1);
myTree.insert([2, 3, 4, null, null, 5]);
console.log(myTree);
.as-console-wrapper { max-height: 100% !important; top: 0; }
基于@trincot 的迭代解决方案，下面的代码在输入上循环，而不是在队列上循环。
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
insert(values) {
// clear current children before insert
this.left = this.right = null;
const queue = [this];
for (var i = 0; i < values.length; ) {
const current = queue.shift();
for (let side of ["left", "right"]) {
if (i < values.length && values[i] !== null) {
current[side] = new TreeNode(values[i]);
queue.push(current[side]);
}
++i;
}
}
return this;
}
}
const myTree = new TreeNode(1);
myTree.insert([2,3,4,null,null,5]);
console.log(myTree);
请注意，您将始终从左到右填充节点，并且每个级别都沿着树级别向下（根据您的要求跳过空值）。更深的节点总是新创建的，每个节点只被访问一次。因此，无需检查之前是否设置了 left 或 right 子项。
添加了额外的检查 i < values.length，因为输入数组可能包含奇数个条目（缺少树的最右边的底部元素）。
我会重新设计 insert 函数，以便它在子实例而不是父实例上递归调用 insert。
如果示例数组包含 15 个元素，则它的值位于索引 0-14 处。我们在索引和树中位置之间有一个映射。以下是索引如何映射到具有 15 个节点的完整树：
0
/ \
/ \
/ \
/ \
/ \
1 2
/ \ / \
/ \ / \
3 4 5 6
/ \ / \ / \ / \
7 8 9 10 11 12 13 14
当我们将根节点 #0 告诉 .insert([ 'a', 'b', 'c', 'd', 'e', 'f', ... ]) 时，我们知道节点 #1 获取索引 0 处的值 ('a')，#2 获取索引 1 处的值 ( 'b')，等等。节点 #1 获取索引 0，节点 #2 获取索引 1，节点 #3 获取索引 2...模式是索引 n 是节点 #[= 的值20=]。这是因为索引 0 不是指根节点而是根节点的左子节点。
父节点的索引与其子节点的索引之间存在关系。我们可以称之为 getChildIndices(parIndex):
getChildIndices(0) = [ 1, 2 ];
getChildIndices(1) = [ 3, 4 ];
getChildIndices(2) = [ 5, 6 ];
getChildIndices(3) = [ 7, 8 ];
getChildIndices(4) = [ 9, 10 ];
getChildIndices(5) = [ 11, 12 ];
getChildIndices(6) = [ 13, 14 ];
.
.
.
由于您选择的这个映射具有一定的优雅性，所以功能非常简单：
let getChildIndices = parIndex => [ parIndex * 2 + 1, parIndex * 2 + 2 ];
这样我们就可以写出更优雅的插入函数了：
let getChildIndices = parInd => [ parInd * 2 + 1, parInd * 2 + 2 ];
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
insert(values, myInd=0) {
let [ lInd, rInd ] = getChildIndices(myInd);
let vals = [
{ ind: lInd, prop: 'left' }, // `lInd` corresponds to our "left" property
{ ind: rInd, prop: 'right'} // `rInd` corresponds to our "right" property
];
for (let { ind, prop } of vals) {
// If we're out-of-bounds in `values`, stop!
if ((ind - 1) >= values.length) continue;
// A value of `null` in `values` indicates the subtree is null. Otherwise, a child
// node exists.
let shouldNodeExist = values[ind - 1] !== null;
if (this[prop] && !shouldNodeExist) { // If the node exists and shouldn't...
// Set the node to null
this[prop] = null;
} else if (!this[prop] && shouldNodeExist) { // If the node doesn't exist and should...
// Create a new child node
this[prop] = new TreeNode(null);
}
// Recursively call insert on the new child node, informing it of its index
if (this[prop]) {
this[prop].value = values[ind - 1];
this[prop].insert(values, ind);
}
}
}
}
let tree1 = new TreeNode(1);
tree1.insert([ 2, 3, 4, null, null, 5 ]);
console.log({ tree1 });
let tree2 = new TreeNode(1);
tree2.insert([ 2, null, 4, null, 6, 7 ]);
console.log({ tree2 });
请注意，此 insert 方法允许从树中添加、修改和删除节点。任何包含 null 的索引都会导致其对应的子树被删除。
请注意，如果我们尝试使用此方法指定不连续的子树 - 例如我们在索引 3 和 4 处指定值，但 null 在其父索引 (1) 处，索引 1 处的整个子树将为空，索引 3 和 4 将被忽略。
更新
这可以通过专用的广度优先遍历函数变得更加清晰 (bft。)
const bft = (nodes) =>
nodes .length == 0
? []
: [
...nodes,
...bft(nodes.flatMap (n => n .left ? n.right ? [n.left, n.right] : [n.left] : []))
]
class TreeNode {
constructor (val) {
this.val = val
}
insert (vals) {
return vals.reduce ((
tree, val, _, __,
parent = bft([tree]) .find (n => n.left === void 0 || n.right === void 0) || {}
) =>
((parent [parent.left === void 0 ? 'left' : 'right'] = val === null
? null
: new TreeNode(val)),
tree),
this)
}
}
你可以在下面的片段中看到这种方法：
const bft = (nodes) =>
nodes .length == 0
? []
: [
...nodes,
...bft(nodes.flatMap (n => n .left ? n.right ? [n.left, n.right] : [n.left] : []))
]
class TreeNode {
constructor (val) {
this.val = val
}
insert (vals) {
return vals.reduce ((
tree, val, _, __,
parent = bft([tree]) .find (n => n.left === void 0 || n.right === void 0) || {}
) =>
((parent [parent.left === void 0 ? 'left' : 'right'] = val === null
? null
: new TreeNode(val)),
tree),
this)
}
}
let myTree = new TreeNode (1);
myTree .insert ([2, 3, 4, null, null, 5]);
console .log (myTree);
// Handles subsequent inserts
myTree .insert ([6, null, null, null, 7, 8]);
console .log (myTree);
// Handles blocked nodes
myTree = new TreeNode(1);
myTree.insert([ 2, null, 4, null, 6, 7 ]);
console.log(myTree);
// Fails (somewhat) gracefully when node cannot be inserted
myTree = new TreeNode (1);
myTree .insert ([null, null, null, 2]);
console .log (myTree);
.as-console-wrapper {min-height: 100% !important; top: 0}
原答案
另一种可能性与此处的大多数答案不同。
大多数其他答案只允许一个 insert，此时它也可以折叠到构造函数中。
这个允许多个 inserts。但它不会将 left 和 right 子级设置为 null 除非我们在要插入的值中实际包含 null 。所以一些节点只有一个val，一些节点有一个val和left，而其他节点有一个val，一个left和一个right.通过留下这些洞，我们保留了以后添加其他节点的位置。
这种技术也相当优雅地处理了一切都已满的情况，只是拒绝添加剩余的节点。
class TreeNode {
constructor (val) {
this .val = val
}
insert (vals) {
return vals .reduce ((t, v) => {
const queue = [t]
while (queue .length) {
let node = queue .shift ()
if (node .left === void 0) {
node .left = v === null ? null : new TreeNode(v)
return t
} else if (node .right === void 0) {
node .right = v === null ? null : new TreeNode(v)
return t
} else {
if (node .left !== null) {
queue .push (node .left)
}
if (node .right !== null) {
queue.push (node.right)
}
}
}
return t // If we hit this point, then our insert failed: there's no room left.
}, this)
}
}
let myTree = new TreeNode (1);
myTree .insert ([2, 3, 4, null, null, 5]);
console .log (myTree);
// Handles subsequent inserts
myTree .insert ([6, null, null, null, 7, 8]);
console .log (myTree);
// Handles blocked nodes
myTree = new TreeNode(1);
myTree.insert([ 2, null, 4, null, 6, 7 ]);
console.log(myTree);
// Fails (somewhat) gracefully when node cannot be inserted
myTree = new TreeNode (1);
myTree .insert ([null, null, null, 2]);
console .log (myTree);
.as-console-wrapper {min-height: 100% !important; top: 0}
我们使用队列的广度优先遍历来保持节点仍然要访问，从根开始，如果我们还没有找到我们的插入点，则添加每个非空的左右子节点。
这样做的最大潜在缺点是不能保证任何节点的 left 或 right 子节点确实被定义。我们在这里使用 JS 的两个不同的 nil 值用于不同的目的。 null 表示该子树被阻塞。 undefined 表示虽然它尚不存在，但可以插入。有些人真的不喜欢以这种方式区分这两个 nilary 值。我认为它适用于语言的粒度，但是 YMMV。
这不是我特别引以为豪的代码。我更喜欢从不改变数据结构，而是总是创建新的数据结构。而且我更喜欢尽可能多地使用表达式而不是语句。但是我已经在这上面花了太长时间了，所以我现在不会花时间看看是否可以清理它。如果没有别的，它提供了一种与此处其他答案不同的方法，并解决了他们没有解决的某些问题。