查找二叉搜索树的深度时超过最大递归深度

Question

这是我的代码:

# 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) )

首先，我从一个列表中做一个二叉查找树，并检查它是否是一个二叉查找树。

给定列表的第一个元素是根节点，后续元素成为子节点。无追加到叶节点。

例如，调用 bst_build（[4， 2， 1， 3， 6， 5， 7]） 的结果为：

[4, 
  [2, 
    [1, None, None], 
    [3, None, None]
  ], 
  [6, 
    [5, None, None],
    [7, None, None]]
  ]
]

结果是二叉搜索树，因为左子节点小于父节点，右子节点大于父节点。因此，调用＜code＞bst_child＜/code＞的结果是＜code＞True＜/code>。

然后我添加了寻找二叉查找树深度的代码。通过对第一个列表排序，我制作了两个不同的二分搜索法树。

在本例中，第一个列表是 [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

但是，当列表的长度约为 30 时，它不起作用。排序列表的长度为 30，但结果不是 29，而是其他数字（如 3），否则会发生递归错误：

调用Python对象时超过最大递归深度

因此，我通过添加< code > sys . setrecursionlimit 来增加递归限制。

然后我的代码工作，直到列表的长度大约为40~50。

但是当列表长度超过 50 时，此方法仍然会遇到相同的问题。我也尝试过sys.setrecursionlimit（1000000）或超过数百万，但它没有帮助。

甚至有时什么都不打印。

我怎么能解决这个问题呢？

Answer 1

在二叉树相对平衡的情况下，递归深度不应该太大。尽管如此，即使你的二叉树是退化的，就像当你从一个有序序列(< code>sorted)中创建它时所发生的那样，你仍然只需要O(n)个栈空间。

但是< code>bst_build和< code>find_depth的代码需要更多的堆栈空间。这是因为它们在到达一片叶子时不会原路返回。相反，它们都从根开始重新开始遍历，而不是先退出当前的递归树:

• bst_build通过在想要插入来自 seq 的下一个输入时再次调用 bst_build 来实现此目的。这应该发生在循环中（递归之外），而不是当您已经深入递归树时。
• find_depth通过在到达叶子时再次调用find_depth来做到这一点。这应该通过首先回溯一个步骤，然后再次重复到同级节点来实现。相反，它从根重新开始搜索（这是浪费时间），并且这样做不会先退出递归。

这使得这段代码需要大量的堆栈空间，在最坏的（退化）情况下就像O（n²）。

与您的问题无关，但很遗憾——而且完全没有必要——find_depth在遍历树时破坏它。

另一个与你的问题无关的问题:你的< code>bst_check不正确。对于以下树，它将返回True:

            2
           /
          1
           \
            3

然而，这棵树不是有效的BST。有效 BST 的要求不仅是左子节点小于其父节点，而且左子树中的所有节点都小于该父节点。

以下是所有这些问题的解决方案：

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))