Как написать рекурсию без использования поля класса в Java

Question

У меня есть следующий правильный Java-код, чтобы найти in-order 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

Это избыточно, но здесь идет ... Единственный изменяемый номер классом я мог бы найти в 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 2

Инкапсулировать значение счета в объекте (Integer нецелесообразно, так как он не может быть включен).

Оставить заявку add(int), чтобы увеличить счет; другой, чтобы получить текущее значение.

Передать объект рекурсивно.

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