2

二叉树遍历的递归VS非递归有什么区别？

哪一个最适合一棵大树，为什么？

谢谢

4

2 回答 2

1

递归函数更容易实现，因为您只需要关心一个节点，它们使用堆栈来存储每次调用的状态。

非递归函数的堆栈使用量要少得多，但需要您存储每个级别的所有节点的列表，并且可能比递归函数复杂得多。

于 2012-09-11T13:22:13.910 回答
1

不同之处在于递归方式使用调用堆栈，而迭代方式使用显式堆栈（堆栈数据结构）。这导致了两件事：1）如果是一棵大树，递归的方式会导致堆栈溢出。2）使用迭代方法，您可以在遍历中间的某个地方停止。换句话说，您可以使用堆栈实现类似前序/按序/后序迭代器之类的东西。这在某些情况下可能很有用。

于 2019-11-10T01:05:03.160 回答