使用前序和有序序列重建二进制文件

Question

我写了以下代码，但每次我运行程序，它显示的结果

File "D:\study\ML\binaryTree.py", line 31, in buildTree
    root.left = self.buildTree(preorder[1:rootvalue],inorder[0:rootvalue-1])
File "D:\study\ML\binaryTree.py", line 30, in buildTree
    root = TreeNode(rootvalue)
RuntimeError: maximum recursion depth exceeded`

它必须递归地解决，我真的不知道是什么问题。我写的代码：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

class Solution:
    def buildTree(self, preorder, inorder):
        if preorder == None or inorder == None:
            return None
        if len(preorder) != len(inorder):
            return None

        length = len(preorder)
        rootvalue = 0
        for i in range(0,length):
            if inorder[i] == preorder[0]:
                rootvalue = i
                break
        if rootvalue == length-1 and inorder[rootvalue] != preorder[0]:
            return None
        root = TreeNode(rootvalue)
        root.left = self.buildTree(preorder[1:rootvalue],inorder[0:rootvalue-1])
        root.right = self.buildTree(preorder[rootvalue+1:length],inorder[rootvalue+1:length])
        print root.val,'->'
        return root
if __name__ == '__main__':
    sul = Solution()
    pre = [1,2,3]
    inorder = [2,1,3]
    sul.buildTree(pre,inorder)

Answer 1

您没有任何防止空列表的代码，因此没有递归的基本情况。可能不是使用preorder == None or inorder == None测试，而是使用if not preorder or not inorder（因为如果列表是空的，那么它们就是“false”）。你知道吗