java - Javaでクラスフィールドを使わずに再帰を書く方法

Question

k二分木で順番に th 要素を見つけるための次の正しい Java コードがあります。

private static int count = 0;
public static <T> T findkthInOrder(Node<T> root, int k) {
    count=0;
    return findkthInOrder(root, k, 0);
}
public static <T> T findkthInOrder(Node<T> root, int k,int a) {
    if (root == null)
        return null;
    T rt = findkthInOrder(root.left, k, 0);
    if (rt != null)
        return rt;
    count++;
    if (count == k) {
        return root.data;
    }
    return findkthInOrder(root.right, k, 0);
}

countしかし、おそらく追加のメソッド引数を使用して、の使用を本当に削除したいと考えています。また、再帰として保持し、メソッドが型の値findkthInOrderを返すことを要求します。T

誰でもこれで私を助けてもらえますか? ありがとうございました。

Answer 1

public class Node< T > {
    T tData;
    Node< T > ntLeft, ntRight;
    int iSubtreeCount;
    public Node( T tData, Node< T > ntLeft, Node< T > ntRight ) {
        this.tData = tData;
        this.ntLeft = ntLeft;
        this.ntRight = ntRight;
        this.iSubtreeCount = subCount( ntLeft ) + subCount( ntRight ) + 1;
    }
    public static int subCount( Node< T > nt ) {
        return null == nt ? 0 : nt.getSubtreeCount();
    }
    public int getSubtreeCount() { return iSubtreeCount; }
    public Node< T > getLeft() { return ntLeft; }
    public Node< T > getRight() { return ntRight; }
    public T getData() { return tData; }
}

そしてあなたのルーチン：

public static < T > T findKth( Node< T > ntInput, int k ) {
    if ( 0 == k || null == ntInput )
        return null;
    else if ( Node.subCount( ntInput.getLeft() ) > k - 1 )
        return findKth( ntInput.getLeft(), k );
    else if ( Node.subCount( ntInput.getLeft() ) == k - 1 )
        return ntInput.getData();
    else
        return findKth( ntInput.getRight(), k - 1 - Node.subCount( ntInput.getLeft() ) );
}

Answer 2

カウント値をオブジェクトにカプセル化します (Integer不変なので役に立ちません)。

add(int)カウントを増やすメソッドを追加します。もう1つは現在の値を取得します。

オブジェクトを再帰的に渡します。