Python树遍历递归深度超过限制。

Question

我有一个区间树，它保存了一段数字范围内的数据（使用这里介绍的数据结构）。以下是代码：

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, e, data, L, R)

        self.root = _init(1, N)

这个递归方法在 N 约为 300 时会出现超过最大递归深度的错误。有没有一种迭代方式来创建树而不是递归？

- knite

Answer 1

真正的问题不是你算法的递归深度，对于像300这样的值应该约为10，而是你在使用is比较数字。 is关键字检查对象的身份，而==检查相等性：

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

因此，您的if条件应该终止递归，但实际上永远不会为真，函数将保持递归，即使b和e相等。如果更改if，则可以解决此问题。

if b == e:
   ...

对于小数字，这个问题可能不会出现，因为Python使用缓存并重复使用对象，适用于大小在一定范围内的整数。

- sth

Answer 2

通常，从递归转换为迭代的方法是手动维护堆栈（或队列）。

类似以下方式：

 while stack is not empty:
     item = pop from stack

     do processing (such as adding onto the node)

     push L and R onto the stack

栈在内存中确实会增长，因为对于每个弹出的项，您都会推入两个。

- Donald Miner

---

是的，我想这样做，但我需要在（递归地）创建L和R节点后在当前节点上执行处理。 我不确定如何/在哪里存储当前节点以供将来处理 - 在一个单独的堆栈上？ - knite

通常有更好的方法来实现树遍历（虽然它们可能会涉及指针操作等复杂内容），而不是使用“堆栈”。毕竟，如果您在堆上使用堆栈，您并没有真正节省太多空间（除了需要保存较少状态的常数因素之外）。 - Voo