Python树遍历递归深度超出

发布时间：2020-12-20 11:21:02 所属栏目：Python 来源：网络整理

导读：我有一个段树,它保存一系列数字的数据(数据结构选择 here).这是代码： class SegmentTree: def __init__(self,N): def _init(b,e): if b is e: data = foo() # No dependency return Node(b,e,data,None,None) else: mid = (b + e ) / 2 L = _init(b,mid) R

我有一个段树,它保存一系列数字的数据(数据结构选择 here).这是代码：

class SegmentTree:
    def __init__(self,N):
        def _init(b,e):
            if b is e:
                data = foo() # No dependency
                return Node(b,e,data,None,None)
            else:
                mid = (b + e ) / 2

                L = _init(b,mid)
                R = _init(mid + 1,e)

                data = foo() #Data depends on L and R

                return Node(b,L,R)

        self.root = _init(1,N)

对于大约300的N,超过最大递归深度超出错误时,这会失败.有没有办法迭代地而不是递归地创建树？

解决方法

真正的问题不是算法的递归深度,对于像300这样的值,它应该是大约10,但是你要将数字与is进行比较. is关键字检查对象标识,而==检查相等性：

>>> 300 == 299+1
True
>>> 300 is 299+1
False

因为你的if条件应该终止递归永远不会成立,函数将继续递归,即使b和e相等.

如果你改变了,如果这个问题应该消失：

if b == e:
   ...

对于较小的数字,问题可能不会发生,因为Python “caches” and reuses the objects的内容达到一定的大小.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!