我尝试使用以下代码创建 BST,nums = [4,5,8,2]
var TreeNode = function (val) {
this.val = val;
this.left = this.right = null;
this.count = 1;
}
var constructBST = function(nums) {
if (nums.length === 0) return null;
let root = new TreeNode(nums[0]);
for (let i = 1; i < nums.length; i++) {
let currentNode = root;
while (currentNode) {
if (currentNode.val > nums[i]) {
currentNode = currentNode.left;
} else if (currentNode.val < nums[i]) {
currentNode = currentNode.right;
}
}
currentNode = new TreeNode(nums[i]);
}
console.log(root);
return root;
}
我每次迭代都将root作为当前节点,并根据值移动currentNode,但是当我迭代数组后打印出root时,为什么我的根节点没有改变?
这是输出:
TreeNode { val: 4, right: null, left: null, count: 1 }、
编辑:假设我有一个根节点 3,并且它没有子节点,当我将当前节点设置为根时,并且如果我移动 currentNode = currentNode.left; 这不是说明currentNode和root之间有联系吗?我认为 currentNode 现在代表 root 的左子节点。如果我对 currentNode 进行任何更改,根的左子节点也会更改
最佳答案
您似乎正确地浏览了树,但新创建的节点从未连接到其预期的父节点。更改函数如下。
var constructBST = function(nums) {
if (nums.length === 0) return null;
let root = new TreeNode(nums[0]);
for (let i = 1; i < nums.length; i++) {
let currentNode = root;
while (currentNode) {
if (currentNode.val > nums[i]) {
if (null == currentNode.left) {
currentNode.left = new TreeNode(nums[i]);
currentNode = null;
} else {
currentNode = currentNode.left;
}
} else if (currentNode.val < nums[i]) {
if (null == currentNode.right) {
currentNode.right = new TreeNode(nums[i]);
currentNode = null;
} else {
currentNode = currentNode.right;
}
}
}
}
console.log(root);
return root;
}
关于javascript - 代码无法使用数字数组创建 BST,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50849277/