从字符串反序列化二进制搜索树

Question

刚刚练习并注意到序列化(通过深度优先搜索遍历)bst并将其反序列化回树中很容易。但是，如果序列化是通过面包优先搜索遍历完成的，那么我很难对它进行反序列化。

例如，给定的输入：5，2，11，N，3，7，19，N，N，6，8，N，N，N寻找输出-

5
/   
2     11
/     /  
N   3  7    19
/     / 
6   8  N   N
/  / 
N  N N N

Answer 1

记住，这是二进制树搜索，这意味着每个节点只有两个子节点，左和右。

(假设N代表空/无节点)：建立你的树。输入序列中的第一个元素是根元素，接下来的两个元素分别指定为根的左子元素和右子元素。然后使用bfs去你的树。如果子节点是N，则转到下一个子节点；如果子节点为值，则将输入序列中的下两个值指定为该节点的左右子节点。等等。

示例：
5,2,11，N，3,7,19，N，N，6,8，N，N，N，N
将5指定为根

将5视为节点->它是一个值，分配子级：
2,11，N，3,7,19，N，6,8，N，N，N，N，N//5处理后的剩余输入
将2分配为左子级
11，N，3,7,19，N，N，6,8，N，N-，N，N
将11指定为右侧子项
//在深度0完成整个宽度

将2视为节点->它是一个值，分配子级：
N，3,7,19，N，N，6,8，N，N，N，N
将N分配为左子级
3,7.19，N，N，6,8，N，N，N，N
将3指定为右侧子项

考虑11作为节点->它是一个值，分配子级：
7,19，N，N，6,8，N，N，N，N
分配7作为左子级
19，N，N，6,8，N，N-，N，N
将19指定为右侧子项
//完成深度1的整个宽度

考虑N作为节点->不是一个值，继续到下一个广度节点
将3视为节点->它是一个值，分配子级：
N，N，6,8，N，N、N、N，N
将N分配为左子级
N，6,8，N，N，N-，N，N
将N指定为右子项

将7视为节点->。。。等等

在分析输入字符串的同时构建一棵树，并使用广度优先搜索来到达该构建树中的下一个叶子，如果它有一个有效值，则它会将输入字符串中的下两个元素分配为左和右子元素。

Answer 2

要取消通过广度优先遍历生成的字符串的序列化，基本上使用相同的机制。使用一个队列，在该队列上放置应该注入新子项的引用。在注入新的子节点时，在队列上再添加两个引用，每个子节点一个引用。

由于队列是FIFO，所以子级的注入将按广度优先顺序进行。

以下是它在Python中的样子：

def to_tree(serialised):
container = [None]
leaves = [[container, 0]] # put the reference to the root on the queue
for value in serialised.split(","):
children, childIndex = leaves.pop(0) # pull from queue
if value != 'N':
node = children[childIndex] = {
"value": value,
"children": [None, None]
}
# append the new 2 child references to the queue
leaves.append([node["children"], 0])
leaves.append([node["children"], 1])
if len(leaves) == 0: # should not happen if input is complete
break 
return container[0] # return the root
# Example call
tree = to_tree("5,2,11,N,3,7,19,N,N,6,8,N,N,N,N,N,N")
# Output the result in JSON format
import json
print(json.dumps(tree, indent=2))

上述输出为：

{
"value": "5",
"children": [
{
"value": "2",
"children": [
null,
{
"value": "3",
"children": [
null,
null
]
}
]
},
{
"value": "11",
"children": [
{
"value": "7",
"children": [
{
"value": "6",
"children": [
null,
null
]
},
{
"value": "8",
"children": [
null,
null
]
}
]
},
{
"value": "19",
"children": [
null,
null
]
}
]
}
]
}