小编ash*_*win的帖子

所以我在研究树遍历算法。例如，在 Kd 树遍历中，我们的目标是将节点向下遍历到叶子节点。这与其说是树搜索，不如说是从根到叶的遍历。

在这种情况下，递归解决方案就足够了。但是，在像 C 这样的语言中，递归调用函数需要将值压入堆栈并在堆栈帧之间跳转等。标准递归方法类似于：

void traverse(Node* ptr){
    if(ptr.left == null && ptr.right == null) return;
    if(ptr.val >= threshold) traverse(ptr.right);
    else if(ptr.val < threshold) traverse(ptr.left);
}
traverse(root);

因此，考虑到二叉树有一个明确的上限（我相信这也可以扩展到其他树类型），以迭代方式执行此遍历是否会更有效：

Node* ptr = root;
for(int i = 0; i < tree.maxHeight; i++) {
    if (ptr.left == null && ptr.right == null) break;
    if (ptr.val >= threshold) ptr = ptr.right;
    else if (ptr.val < threshold) ptr = ptr.left
}

二叉树的最大高度将是它的节点数，而平衡的将是 log(n)。因此，我想知道迭代解决方案是否有任何缺点，或者它是否确实比简单的递归更快。我在这方面缺少任何概念吗？