Параметр рекурсии Java

Question

Я пишу рекурсивный вызов, чтобы увидеть, находятся ли два узла (n & m) внутри поддерева в двоичном дереве. Вот функция:

public static boolean containsNodes(int n, int m, TreeNode node, int count){ 
    if(node == null) return false; 
    if(count == 2) return true; 
    if(node.getData() == m || node.getData() == n){ 
     count++; 
    } 
    return containsNodes(n, m, node.getLeft(), count) || 
      containsNodes(n, m, node.getRight(), count); 

} 

Это выглядит подсчитывать любит никогда не получать обновляется в дальнейшем вызывает даже если условие node.getData() == m || node.getData() == n верно. Почему это так?

Answer 1

Этот код вернётся, даже если вы найдете n или m дважды. Верните «маску» вместо boolean и установите бит 0, когда найдете m и бит 1, когда найдете n. Добавить обертку, которая возвращает true для «маски» 3, и false для всего остального:

public static boolean containsNodes(int n, int m, TreeNode node) { 
    return containsNodesMask(n, m, node, 0) == 3; 
} 
private static int containsNodesMask(int n, int m, TreeNode node, int mask) { 
    if (node == null) return mask; 
    if (node.getData() == m) mask |= 2; 
    if (node.getData() == n) mask |= 1; 
    if (mask == 3) return mask; // Short-circuit 
    mask = containsNodes(n, m, node.getLeft(), mask); 
    if (mask == 3) return mask; // Short-circuit again 
    return containsNodes(n, m, node.getRight(), mask); 
}