查找二叉搜索树的深度时超过最大递归深度
Maximum recursion depth exceeded when finding the depth of binary-search-tree
这是我的代码：
# increase the limit of recursion
import sys
sys.setrecursionlimit(100000)
import numpy as np
# make binary search tree from list
def bst_build(seq):
binary_search_tree = [seq[0], None, None]
seq.pop(0)
def add_child(main, sub):
if len(sub) != 0:
if main[0] > sub[0]:
if main[1] == None:
main.pop(1)
main.insert(1, [sub[0], None, None])
sub.pop(0)
add_child(binary_search_tree, sub)
else:
add_child(main[1], sub)
elif main[0] < sub[0]:
if main[2] == None:
main.pop(2)
main.insert(2, [sub[0], None, None])
sub.pop(0)
add_child(binary_search_tree, sub)
else:
add_child(main[2], sub)
else:
sub.pop(0)
else:
pass
add_child(binary_search_tree, seq)
return binary_search_tree
# check the correctness
def bst_check(b):
if b is None: return True
if b[1] is not None:
if b[1][0] >= b[0]: return False
if bst_check(b[1]) == False: return False
if b[2] is not None:
if b[2][0] <= b[0]: return False
if bst_check(b[2]) == False: return False
return True
# find depth of binary search tree
def bst_depth(b):
maximum_depth = 0
current_depth = 0
def find_depth(tree):
nonlocal maximum_depth
nonlocal current_depth
if len(tree) != 1:
if tree[1] != None and len(tree[1]) != 1:
current_depth += 1
find_depth(tree[1])
else:
tree.pop(1)
if maximum_depth <= current_depth:
maximum_depth = current_depth
current_depth = 0
find_depth(b)
else:
pass
find_depth(b)
return maximum_depth
unsorted = list(np.random.randint(0,100,10))
sorted = unsorted.copy()
sorted.sort()
t1 = bst_build(unsorted)
t2 = bst_build(sorted)
print(t1)
print(t2)
print(bst_check(t1), bst_check(t2))
print( bst_depth(t1), bst_depth(t2) )
首先，我从列表中创建一个二叉搜索树，并检查它是否是一个二叉搜索树。
给定列表的第一个元素是根节点，后面的元素成为子节点。 None 附加到叶节点。
例如调用bst_build([4, 2, 1, 3, 6, 5, 7])的结果是：
[4,
[2,
[1, None, None],
[3, None, None]
],
[6,
[5, None, None],
[7, None, None]]
]
]
结果是二叉搜索树，因为左子节点小于父节点，右子节点大于父节点。因此调用 bst_child 的结果是 True.
然后我添加了查找二叉搜索树深度的代码。
我通过对第一个列表进行排序，制作了两个不同的二叉搜索树。
在这种情况下，第一个列表是[4,2,1,3,6,5,7]，第二个列表是[1,2,3,4,5,6,7]，已排序。
从第一个列表构建的二叉搜索树的深度为2，而从排序列表构建的二叉搜索树的深度为6。
unsorted = [4,2,1,3,6,5,7]
sorted = unsorted.copy()
sorted.sort()
t1 = bst_build(unsorted)
t2 = bst_build(sorted)
print(t1)
print(t2)
print(bst_check(t1), bst_check(t2))
print( bst_depth(t1), bst_depth(t2) )
输出是（在漂亮地打印嵌套列表之后）：
[4,
[2,
[1, None, None],
[3, None, None]
],
[6,
[5, None, None],
[7, None, None]]
]
]
[1, None,
[2, None,
[3, None,
[4, None,
[5, None,
[6, None,
[7, None, None]
]
]
]
]
]
]
True True
2 6
我认为我把二叉搜索树和代码查找深度做得很好。
但是当我尝试使用长列表时，我的 vscode 无法打印正确的结果。
当我尝试使用长度为 20 的列表时，它成功了。
unsorted = list(np.random.randint(0,1000,20))
sorted = unsorted.copy()
sorted.sort()
t1 = bst_build(unsorted)
t2 = bst_build(sorted)
print(bst_check(t1), bst_check(t2))
print( bst_depth(t1), bst_depth(t2) )
输出：
True True
5 19
但是，当list的长度在30左右时，是不行的。
排序后的列表长度为30，但结果不是29而是其他一些数字，比如3，或者出现递归错误：
maximum recursion depth exceeded while calling a Python object
所以我通过添加 sys.setrecursionlimit.
增加了递归限制
然后我的代码一直工作到列表的长度大约为 40~50。
但是当列表长度超过50时，这种方法仍然会出现同样的问题。我也尝试过 sys.setrecursionlimit(1000000) 或超过数百万，但它没有帮助。
甚至有时什么都不打印。
我该如何解决这个问题？
在你的二叉树比较平衡的情况下，递归深度不要太大。尽管如此，即使您的二叉树是 退化 ，就像您从排序序列 (sorted) 创建它时发生的情况一样，您仍然应该只需要 O(n) 堆栈space.
但是 bst_build 和 find_depth 的代码需要更多堆栈 space。这是因为它们在到达叶子时不会原路返回。相反，他们都从 root 重新开始遍历，而没有首先离开 current 递归树：
bst_build 通过在想要插入来自 seq 的下一个输入时再次调用 bst_build 来实现这一点。这应该发生在一个循环中（在递归之外），而不是当你已经深入递归树时。find_depth 通过在到达叶子时再次调用 find_depth 来实现。这应该通过首先回溯一个步骤然后再次出现在同级节点中来实现。相反，它会从根部重新开始搜索（这是浪费时间），并且不会先退出递归。
这使得此代码需要大量堆栈 space，在最坏（退化）的情况下就像 O(n²)。
与您的问题无关，但遗憾的是 - 完全没有必要 - find_depth 在遍历树时破坏了树。
另一个与你的问题无关的问题：你的bst_check不正确。对于以下树，它将 return 为真：
2
/
1
\
3
但是，这棵树不是有效的 BST。有效 BST 的要求不仅是左 child 小于其 parent，而且 左子树中的所有节点 都小于 parent.
以下是所有这些问题的修复方法：
def bst_build(seq):
if not seq:
return None
def add_child(main, value):
if value == main[0]:
return
childindex = 1 if main[0] > value else 2
if not main[childindex]:
main[childindex] = [value, None, None]
else:
add_child(main[childindex], value)
binary_search_tree = [seq[0], None, None]
for value in seq[1:]:
add_child(binary_search_tree, value)
return binary_search_tree
def bst_depth(b):
return 1 + max(bst_depth(b[1]) if b[1] else -1, bst_depth(b[2]) if b[2] else -1)
def bst_check(b, low=float("-inf"), high=float("inf")):
return not b or (low <= b[0] <= high and bst_check(b[1], low, b[0])
and bst_check(b[2], b[0], high))
这是我的代码：
# increase the limit of recursion
import sys
sys.setrecursionlimit(100000)
import numpy as np
# make binary search tree from list
def bst_build(seq):
binary_search_tree = [seq[0], None, None]
seq.pop(0)
def add_child(main, sub):
if len(sub) != 0:
if main[0] > sub[0]:
if main[1] == None:
main.pop(1)
main.insert(1, [sub[0], None, None])
sub.pop(0)
add_child(binary_search_tree, sub)
else:
add_child(main[1], sub)
elif main[0] < sub[0]:
if main[2] == None:
main.pop(2)
main.insert(2, [sub[0], None, None])
sub.pop(0)
add_child(binary_search_tree, sub)
else:
add_child(main[2], sub)
else:
sub.pop(0)
else:
pass
add_child(binary_search_tree, seq)
return binary_search_tree
# check the correctness
def bst_check(b):
if b is None: return True
if b[1] is not None:
if b[1][0] >= b[0]: return False
if bst_check(b[1]) == False: return False
if b[2] is not None:
if b[2][0] <= b[0]: return False
if bst_check(b[2]) == False: return False
return True
# find depth of binary search tree
def bst_depth(b):
maximum_depth = 0
current_depth = 0
def find_depth(tree):
nonlocal maximum_depth
nonlocal current_depth
if len(tree) != 1:
if tree[1] != None and len(tree[1]) != 1:
current_depth += 1
find_depth(tree[1])
else:
tree.pop(1)
if maximum_depth <= current_depth:
maximum_depth = current_depth
current_depth = 0
find_depth(b)
else:
pass
find_depth(b)
return maximum_depth
unsorted = list(np.random.randint(0,100,10))
sorted = unsorted.copy()
sorted.sort()
t1 = bst_build(unsorted)
t2 = bst_build(sorted)
print(t1)
print(t2)
print(bst_check(t1), bst_check(t2))
print( bst_depth(t1), bst_depth(t2) )
首先，我从列表中创建一个二叉搜索树，并检查它是否是一个二叉搜索树。
给定列表的第一个元素是根节点，后面的元素成为子节点。 None 附加到叶节点。
例如调用bst_build([4, 2, 1, 3, 6, 5, 7])的结果是：
[4,
[2,
[1, None, None],
[3, None, None]
],
[6,
[5, None, None],
[7, None, None]]
]
]
结果是二叉搜索树，因为左子节点小于父节点，右子节点大于父节点。因此调用 bst_child 的结果是 True.
然后我添加了查找二叉搜索树深度的代码。 我通过对第一个列表进行排序，制作了两个不同的二叉搜索树。
在这种情况下，第一个列表是[4,2,1,3,6,5,7]，第二个列表是[1,2,3,4,5,6,7]，已排序。
从第一个列表构建的二叉搜索树的深度为2，而从排序列表构建的二叉搜索树的深度为6。
unsorted = [4,2,1,3,6,5,7]
sorted = unsorted.copy()
sorted.sort()
t1 = bst_build(unsorted)
t2 = bst_build(sorted)
print(t1)
print(t2)
print(bst_check(t1), bst_check(t2))
print( bst_depth(t1), bst_depth(t2) )
输出是（在漂亮地打印嵌套列表之后）：
[4,
[2,
[1, None, None],
[3, None, None]
],
[6,
[5, None, None],
[7, None, None]]
]
]
[1, None,
[2, None,
[3, None,
[4, None,
[5, None,
[6, None,
[7, None, None]
]
]
]
]
]
]
True True
2 6
我认为我把二叉搜索树和代码查找深度做得很好。 但是当我尝试使用长列表时，我的 vscode 无法打印正确的结果。
当我尝试使用长度为 20 的列表时，它成功了。
unsorted = list(np.random.randint(0,1000,20))
sorted = unsorted.copy()
sorted.sort()
t1 = bst_build(unsorted)
t2 = bst_build(sorted)
print(bst_check(t1), bst_check(t2))
print( bst_depth(t1), bst_depth(t2) )
输出：
True True
5 19
但是，当list的长度在30左右时，是不行的。 排序后的列表长度为30，但结果不是29而是其他一些数字，比如3，或者出现递归错误：
maximum recursion depth exceeded while calling a Python object
所以我通过添加 sys.setrecursionlimit.
然后我的代码一直工作到列表的长度大约为 40~50。
但是当列表长度超过50时，这种方法仍然会出现同样的问题。我也尝试过 sys.setrecursionlimit(1000000) 或超过数百万，但它没有帮助。
甚至有时什么都不打印。
我该如何解决这个问题？
在你的二叉树比较平衡的情况下，递归深度不要太大。尽管如此，即使您的二叉树是 退化 ，就像您从排序序列 (sorted) 创建它时发生的情况一样，您仍然应该只需要 O(n) 堆栈space.
但是 bst_build 和 find_depth 的代码需要更多堆栈 space。这是因为它们在到达叶子时不会原路返回。相反，他们都从 root 重新开始遍历，而没有首先离开 current 递归树：
bst_build通过在想要插入来自seq的下一个输入时再次调用bst_build来实现这一点。这应该发生在一个循环中（在递归之外），而不是当你已经深入递归树时。find_depth通过在到达叶子时再次调用find_depth来实现。这应该通过首先回溯一个步骤然后再次出现在同级节点中来实现。相反，它会从根部重新开始搜索（这是浪费时间），并且不会先退出递归。
这使得此代码需要大量堆栈 space，在最坏（退化）的情况下就像 O(n²)。
与您的问题无关，但遗憾的是 - 完全没有必要 - find_depth 在遍历树时破坏了树。
另一个与你的问题无关的问题：你的bst_check不正确。对于以下树，它将 return 为真：
2
/
1
\
3
但是，这棵树不是有效的 BST。有效 BST 的要求不仅是左 child 小于其 parent，而且 左子树中的所有节点 都小于 parent.
以下是所有这些问题的修复方法：
def bst_build(seq):
if not seq:
return None
def add_child(main, value):
if value == main[0]:
return
childindex = 1 if main[0] > value else 2
if not main[childindex]:
main[childindex] = [value, None, None]
else:
add_child(main[childindex], value)
binary_search_tree = [seq[0], None, None]
for value in seq[1:]:
add_child(binary_search_tree, value)
return binary_search_tree
def bst_depth(b):
return 1 + max(bst_depth(b[1]) if b[1] else -1, bst_depth(b[2]) if b[2] else -1)
def bst_check(b, low=float("-inf"), high=float("inf")):
return not b or (low <= b[0] <= high and bst_check(b[1], low, b[0])
and bst_check(b[2], b[0], high))