二叉树的递归遍历和非递归遍历

Question

据我所知，递归算法需要用栈数据结构实现，那二叉树的递归算法实际上仍然是用了递归。可是非递归遍历是直接创建栈和队列来实现遍历。
递归遍历和非递归遍历都是用了栈来实现，那为何说非递归遍历执行效率更高呢？或者请问这两种遍历有什么本质的区别吗？
（可能我对递归理解有误，还请指正）

Answer 1

该回答引用chatgpt:
对于二叉树的遍历，递归算法和非递归算法都需要使用栈或队列数据结构。但是它们的本质区别在于递归算法是基于函数调用栈实现的，而非递归算法则是使用显式栈或队列数据结构来模拟递归调用的过程。

具体来说，递归遍历二叉树是通过函数调用栈实现的，每次递归都会将函数调用压入栈中，直到递归结束返回时才弹出栈，因此递归遍历具有天然的深度优先特点。而非递归遍历则需要手动创建栈或队列数据结构来保存待遍历的节点，从而实现遍历。由于栈和队列数据结构的操作都是基于指针的，相比于函数调用栈的操作，栈和队列数据结构的操作通常会更快。

总体来说，非递归遍历相对于递归遍历来说更具有可控性和效率优势，因此在实际应用中更加常见。但是在某些情况下，递归遍历也具有一些独特的优点，例如实现起来简单、易于理解等。因此，在具体问题和场景中需要根据实际需求和效率要求来选择适当的遍历方法。