java - 树遍历 - 中序位置

Question

我正在尝试使用递归顺序遍历来查找树中 kth 节点的值。

下面的代码是用递归完成的，但我的实现速度太慢了。

有人可以给我提示如何让它更快吗？ (reihe和pos是类变量，都是从0开始，我把最后的结果保存在pos中)。

这是我到目前为止所做的，非常感谢任何帮助:

void valueAtPosition(int k) {

            if(this.left!=null){
                left.valueAtPosition(k);
            }
            if(reihe++==k){
                pos=this.elem;

            }

           else if(this.right!=null){
                right.valueAtPosition(k);
            }
        }

Answer 1

删除 reihe 的需要(我假设它不是英文的，因为它对我来说作为变量名毫无意义)。我已将变量 k 作为返回值传递。当它达到 0 时，我返回当前值并停止搜索。

int valueAtPosition(int k) {

    if(this.left!=null k >= 0){
        k = left.valueAtPosition(k);
    }

    if(k == 0){
        pos=this.elem;
    }
    k--;

    if(this.right!=null && k > 0){
        k = right.valueAtPosition();
    }

    return k;
}