递归与迭代树遍历

因此，我正在研究树遍历算法。例如，在遍历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）。因此，我想知道迭代解决方案是否有任何缺点，或者它确实比纯递归更快。有什么我想念的吗？