c++ - 二叉搜索树前序遍历，递归与循环？

Question

我们可以像这样通过递归遍历二叉搜索树:

void traverse1(node t) {
    if( t != NULL) {
        visit(t);
        traverse1(t->left);
        traverse1(t->right);
    }
}

还有通过循环(带堆栈)，如:

void traverse2(node root) {
    stack.push(root);
    while (stack.notEmpty()) {
        node next = stack.pop();
        visit(next);
        if (next->right != NULL)
            stack.push(next->right);
        if (next->left != NUll)
            stack.push(next->left)
    }
}

问题

哪个效率更高？为什么？

我认为这两种方法的时间复杂度都是O(n)。所以所有的差异都在空间复杂度或..？

Answer 1

这将取决于您如何定义效率？它是在运行时、代码量、可执行文件的大小、使用了多少内存/堆栈空间，或者理解代码的难易程度？

递归非常容易编写代码，希望易于理解，并且代码更少。循环可能有点复杂(取决于你如何看待复杂性)和代码。递归可能更容易理解，并且代码量和可执行文件大小会更少。假设你有几个项目要横向，递归将使用更多的堆栈空间。

循环将有更多的代码(如上面的示例所示)，并且可能被认为更复杂一些。但是横向只是一次调用，而不是多次调用。因此，如果您有很多项目要横向处理，循环会更快，因为您没有时间将项目压入堆栈并将它们弹出，而这正是使用递归时会发生的情况。