使用序和中序序列重建一個二叉樹

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（因爲如果它們是空的，列表是「falsey」）。