输入是具有空值的预序序列化 BST。这些值已被读入具有整数和空值的数组。
示例输入
[ 6, 3, null, null, 8, null, 9, null, null ]
想要的输出
{ _root:
{ value: 6,
left: { value: 3,
left: null,
right: null },
right: { value: 8,
left: null,
right: { value: 9,
left: null,
right: null } } } }
这是 BST 的基本界面:
function BinarySearchTree() {
this._root = null;
}
BinarySearchTree.prototype = {
//restore constructor
constructor: BinarySearchTree,
insert: function(value) {
//create a new item object, place data in
var node = {
value: value,
left: null,
right: null
},
current;
// more code (works, but omitted for this question)
}
};
我们如何反序列化上述输入,以便我们最终得到一个 BinarySearchTree?这会是沿着这些路线的递归预序遍历吗?
function deserialize(arr) {
var result = new BinarySearchTree();
result._root = arr[0];
if (arr[1] === null) {
result._root.left = null;
}
if () {
return null;
}
node.left = deserialize(arr);
node.right = deserialize(arr);
return result;
}
最佳答案
所以我假设输入结构将是节点 1,左子节点 1,左孙节点 1,...右子节点 1,右孙节点 1,...
我们可以维护一个堆栈来构建树,这有助于轻松检索更高级别,(或者我们可以添加指向每个节点父节点的指针)。
Java代码:
void builTree(Integer input){
Node root = new Node(input[0]);
Node cur = root;
for(int i = 1; i < input.length; i++){
if(cur.count <=1){
cur = update(cur,input[i]);
}else{
while(cur.count == 2){//This while loop may not necessary
cur = cur.parent;
}
cur = update(cur, s, input[i]);
}
}
}
Node update(Node node, Integer input){
if(node.count == 0){
node.left = new Node(input);
node.left.parent = node;
node.count++;
if(input != null){
return node.left;
}
}else if(node.count == 1){
node.right = new Node(input);
node.right.parent = node;
node.count++;
if(input != null){
return node.right;
}
}
return node;
}
class Node{
int value , count;//variable count will tell whether a node is full or not
Node left, right, parent;
}
关于javascript - 在 JavaScript 中反序列化二进制搜索树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24482376/