Подсчет узлов с определенным значением в двоичном дереве

Question

Я пытаюсь найти способ перебора двоичного дерева рекурсивно итеративно и подсчитать, сколько раз находить определенное значение. Одна проблема, с которой я столкнулся, - это root в первом методе.

Node внутренний класс:

private class Node { 

    int data; 
    Node root; 
    Node left; 
    Node right; 
} 

Рекурсивный метод & помощника:

public int valCount(int val) { 
    if (root != null) { 
     return valCount(val, root); 
    } 
    return 0; 
} 

public int valCount(int val, Node root) { 
    int cnt = 0; 
    if (root.left != null) { 
     if (root.left.data == val) { 
      cnt++; 
     } 
     valCount(val, root.left); 
    } 


    if (root.right != null) { 
     if (root.right.data == val) { 
      cnt++; 
     } 
     valCount(val, root.right); 
    } 
    return cnt; 
} 

Я не был в состоянии проверить из корня вопроса, так что я не совсем уверен, что мой выход будет быть верным. Итак, вопрос требует, чтобы его спросили ... я даже на правильном пути? Мой подход даже имеет смысл? Любая помощь была бы потрясающей. Ура!

Answer 1

Каждый раз, когда valCount это называют, отдельный копию локальной переменной cnt создается. Таким образом, когда вы вызываете valCount для корня, это создает переменную cnt; когда то valCount называет себя для левого или правого поддерева, новый valCount имеет свой собственный cnt, поэтому, когда они увеличивают cnt, они не увеличивают cnt, что первая valCount владеет. Это означает, что вся работа, выполняемая valCount для левого и правого поддеревьев, выбрасывается.

Простым способом исправить это было бы заметить, что при вызове valCount для левого или правого поддерева рекурсивный вызов вернет значение. Вы должны использовать это значение, вместо того, чтобы отказаться результат:

int leftCount = valCount(val, root.left); 

, а затем сделать что-то с leftCount (я дам вам подумать о том, как использовать).

EDIT: еще одно: valCount должны смотреть на root.data, но он не должен смотреть на root.left.data или root.right.data. Пусть рекурсивные вызовы выполняют работу по просмотру данных в поддеревах. Так часто работает рекурсия двоичного дерева.

Answer 2

Вам не нужен «root» в вашем классе Node. «Корень» - это «этот» объект/указатель, не так ли? Передайте еще один параметр «int [] cnt» в valCount. Выполнить cnt как int [1]. Затем в valCount do cnt [0] ++. В вызывающей функции после окончания рекурсии распечатайте cnt [0]. И удалите локальную переменную cnt.