Проверка всех записей данных в двоичном дереве равна

Question

Я использую Java для двоичного дерева (а не двоичного дерева поиска). У меня есть объявления переменных класса и экземпляра:

class intBTNode 
{ 
    private int data; 
    private intBTNode left; 
    private intBTNode right; 

То, что я хочу сделать, это написать метод, который возвращает истину, только если все записи в дереве, равны целевое число или, если дерево пусто. Я написал следующий код:

public static boolean allEqual(intBTNode root, int target) 
{ 
    if (root == null) 
     return true; 
    if (root.data == target && root.left != null) 
     return allEqual(root.left, target); 
    if (root.data == target && root.right != null) 
     return allEqual(root.right, target); 
    return false; 
} 

Я пытаюсь работать мой путь через это, чтобы проверить код, но я не уверен, что я адекватно проверять все узлы (то есть лист). Кроме того, я пытаюсь разработать способ атаковать эту проблему, которая не является рекурсивной или будет более эффективной. Любая помощь или предложения будут оценены.

Answer 1

Вы не адекватно проверяете все узлы.

Проблема в том, что если root.left не является нулевым, то вы никогда не изучаете root.right; так что дерево вроде этого:

 3 
    /\ 
    3 4 

будет неправильно классифицирован как содержащий только цель.

Лучший подход заключается в написании:

public static boolean allEqual(intBTNode root, int target) 
{ 
    return root == null 
     || root.data == target 
      && allEqual(root.left, target) 
      && allEqual(root.right, target); 
} 

Если вы хотите, чтобы избежать рекурсии по некоторым причинам, вы можете сделать это, сохраняя коллекцию узлов, которые вы «обнаружили» (посетив их родителей), но еще не на самом деле «посетили» (путем изучения их data и дети), и постоянно вытягивать узлы из этой коллекции, и посещать их, пока он не пуст:

public static boolean allEqual(intBTNode root, int target) 
{ 
    List<intBTNode> nodesToVisit = new ArrayList<intBTNode>(); 
    nodesToVisit.add(root); 
    while (! nodesToVisit.isEmpty()) { 
     intBTNode node = nodesToVisit.remove(nodesToVisit.size() - 1); 
     if (node == null) 
      continue; 
     if (node.data != target) 
      return false; 
     nodesToVisit.add(node.left); 
     nodesToVisit.add(node.right); 
    } 
    return true; 
} 

(Это на самом деле точно эквивалентно рекурсивная версия, просто используя ArrayList в качестве стека вместо использования стека вызовов.)

Answer 2

Вы должны заменить

if (root.data == target && root.left != null) 
    return allEqual(root.left, target); 
if (root.data == target && root.right != null)  
    return allEqual(root.right, target); 
return false; 

С

return root.data == target && allEqual(root.left, target) && allEqual(root.right, target); 

Поскольку ваш текущий код игнорирует правое поддерево (а также, нулевые чеки являются избыточными, потому что вы проверить каждый раз, если корень нуль)

Что касается исключения рекурсии, вы можете использовать другой цикл while, нажимая дочерние элементы текущего узла в стек (инициализированный с корнем) и всегда выскакивает первый элемент. (Конечно, в то время как data == target)