java - 如何在不使用 Java 中的类字段的情况下编写递归

Question

我有以下正确的 Java 代码来查找k二叉树中的有序元素。

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

将计数值封装在一个对象中（Integer没有用，因为它是不可变的）。

添加add(int)增加计数的方法；另一个获得当前值。

递归传递对象。

Answer 2

这是矫枉过正，但在这里......我可以在Java中找到的唯一可变数字类是java.util.concurrent.atomic.AtomicInteger

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

我进行了过早的优化，现在已修复。

这是替代解决方案：

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

Answer 3

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