BST 的递归与迭代遍历

Question

如果我递归遍历N个节点的二叉树，会占用Nspace个执行栈。如果我使用迭代，我将不得不在显式堆栈中使用 N spaces。

问题是我们是否说递归遍历也像迭代一样使用 O(N) space 复杂性？我说的是某些受内存限制限制的平台上的运行遍历代码。此外，我不是在谈论直接实现迭代（其中任何一种方法都可以），我正在 BST 中实现 KthSmallestElement() 的算法，它使用某种遍历 BST。

就 space 复杂性而言，我应该使用迭代方法还是递归方法，以便我的代码不会在 space 限制内失败？

说清楚：

这是我实现的：

int Solution::kthsmallest(TreeNode* root, int k) {
    stack<TreeNode *> S;
    while(1)
    {
        while(root)
        {
            S.push(root);
            root=root->left;
        }

        root=S.top();
        S.pop();

        k--;
        if(k==0)
            return root->val;

        root=root->right;
    }
}

这是我朋友实现的：

class Solution {
    public:
        int find(TreeNode* root, int &k) {
            if (!root) return -1;
            // We do an inorder traversal here. 
            int k1 = find(root->left, k);
            if (k == 0) return k1; // left subtree has k or more elements.
            k--; 
            if (k == 0) return root->val; // root is the kth element.
            return find(root->right, k); // answer lies in the right node.
        }

        int kthsmallest(TreeNode* root, int k) {
           return find(root, k); // Call another function to pass k by reference.
        }
};

所以这两个哪个更好，怎么样？

Answer 1

如果您关心内存使用，您应该尽量确保您的树是 平衡的，即它的深度小于节点数。具有 N 个节点的完美平衡二叉树的深度为 log₂N（四舍五入）。

这很重要，因为访问二叉树中所有节点所需的内存与树的深度成正比，而不是像你错误地认为的那样与节点数成正比；递归或迭代程序需要 "remember" 从根到当前节点的路径，而不是其他先前访问过的节点。

BST 的递归与迭代遍历

Recursive Vs iterative Traversal of a BST

recursion

iteration

binary-tree

binary-search-tree

space-complexity