这个问题可能看起来像是一个重复的问题,但我在SO和其他地方都没能找到答案。
我想要用 JavaScript 从一个数组和一个非null根节点构建一个不完整二叉树,用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;
但是没有一个返回预期的结果。
我还查看了一些使用Java的解决方案,但答案使用Java中的内置LinkedList,因此我不确定这是否是在JS中正确的方法。
对Scott Sauyet问题的回答:
预期结果为
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
}
const myTree = new TreeNode(1); myTree.insert([2,null,4,null,6,7])
的预期行为是什么?也就是说,如果您不创建应该是其他节点(6
和7
)的父节点的节点(3
),会发生什么? - Scott Sauyet