树遍历 - 中序位置

Question

我试图在树中找到 kth 节点的值，使用递归顺序遍历。

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

有人可以给我提示如何让它更快吗？（reihe和pos是class变量，都是从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 作为 return 值传递。当它到达0时，我return当前值并停止搜索。

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;
}

树遍历 - 中序位置

Tree traversal - inorder position

java

algorithm

tree

position

traversal