检查嵌套列表是否为二进制搜索树

Question

我正在尝试实现一个函数，该函数检查嵌套列表是否为二进制搜索树
例如[50, [44, 30, 48], [80, [66, 60, 67], 88]]，我有这个列表来表示树
树是使用这个逻辑
来表示的

# Tree in nested list
tree1 = ['a', ['b', ['d',[],[]], ['e',[],[]] ], ['c', ['f',[],[]], []] ]
#
tree2 = ['a',         #root
['b',             #left subtree
['d', [], []],   #left child of b - empty lists show that there are no children
['e', [], []] ], #right child of b
['c',             #right subtree
['f', [], []],
[] ]
]

有什么简单、明显的方法可以做到这一点吗。我对python和数据结构相当陌生
我试着用函数is_bst
编写它

def is_bsp(list)     
root = lists[0]
cur_value = 0
level = 0
for i in lists:
print(i)
if isinstance(i, list):
is_bsp(i)

但我不知道如何继续使用这个

输入/输出示例

is_bsp([50, [44, 30, 48], [80, [66, 60, 67], 88]])
=> True
is_bsp([50, [44, 30, 48], [49, [66, 60, 67], 88]])
=> False

Answer 1

我会将树展平为一个序列，然后检查结果是否排序。

def flatten_tree(lst):
if not isinstance(lst, (list, tuple)):
return [lst]
if not lst:
return []
if len(lst) != 3:
raise ValueError(f"expected is [root, left, right], got {lst}")
return [*flatten_tree(lst[1]), lst[0], *flatten_tree(lst[2])]
def is_bsp(tree):
# TODO: if empty: return True
try:
lst = flatten_tree(tree)
return all(a <= b for a, b in zip(lst, lst[1:]))    # is sorted?
except (ValueError, TypeError):
return False

上面的代码不处理空树(不知道它是如何表示的(，也不检查循环引用(恶意输入可能会触发无休止的递归(。