鱼C论坛

 找回密码
 立即注册
查看: 355|回复: 3

递归生成树报错

[复制链接]
发表于 2018-7-18 00:51:14 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None

  7. class Solution:
  8.     def __init__(self):
  9.         self.pre = []
  10.         self.mid = []
  11.     def bt(self, b1, e1, b2, e2):
  12.         #b1,e1前序的始末下标;b2,e2中序的始末下标
  13.         if b1 > e1:
  14.             return None
  15.         #if b1 == e1:
  16.             #return TreeNode(self.pre[b1])
  17.         midloc = -1
  18.         root = TreeNode(self.pre[b1])
  19.         midloc = self.mid.index(self.pre[b1])
  20.         if midloc == -1:
  21.             return None
  22.         c = midloc - b1 #左子树的长度
  23.         #pre: b1、[b1+1:b1+c]、[b1+c+1:e1]
  24.         #mid: [b2:b2+c-1]、b2+c、[b2+c+1:e2]
  25.         root.left = self.bt(b1+1, b1+c, b2, b2+c-1)
  26.         root.right = self.bt(b1+c+1, e1, b2+c+1, e2)
  27.         return root
  28.         
  29.    
  30.     def buildTree(self, preorder, inorder):
  31.         """
  32.         :type preorder: List[int]
  33.         :type inorder: List[int]
  34.         :rtype: TreeNode
  35.         """
  36.         self.pre = preorder #这个变量不能被bt函数访问到吗
  37.         self.mid = inorder
  38.         return self.bt(0, len(self.pre)-1, 0, len(self.mid)-1)
  39.         
  40.         
复制代码

如上述代码所示,有前序遍历和中序遍历生成树的结构
错误如下:Line 19: RecursionError: maximum recursion depth exceeded
这是哪里出了问题?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-7-18 08:39:09 | 显示全部楼层

回帖奖励 +1 鱼币

有去无回的递归
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-7-18 10:22:42 | 显示全部楼层
我知道错误了啦,第23行应该是c = midloc - b2
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-7-18 10:24:03 | 显示全部楼层
BngThea 发表于 2018-7-18 08:39
有去无回的递归

这个递归并不是有去无回的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 16:41

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表