Я искал эту проблему раньше, но мне кажется, что поиск ответов на предыдущие проблемы мне не помогает, и я не уверен, как проверить свою функцию в двоичном дереве, потому что вы не можете добавить в двоичный файл дерево (я думаю?)
В принципе, для примеров практики для предстоящего экзамена, мой профессор поставил перед нами задачу составить список из всех возможных путей к нулевому узлу. Если путь включает в себя переход влево, поместите 0 в список массивов, а если путь идет вправо, введите 1.
Например:
В двоичном дереве, которое печатается как:
7
- 1
---- 2
------ нуль
------ нуль
---- 3
------ нуль
------ нуль
- нуль
функция должна выдавать:
[[0,0,0], [0,0,1], [0,1,0], [0,1,1], [1]].
Код, который я сделал:
public ArrayList<ArrayList<Integer>> paths() {
return paths(root);
}
public ArrayList<ArrayList<Integer>> newPath(Node<E> n, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> allPaths) {
Node<E> current = n;
//ArrayList<Integer> path = new ArrayList<Integer>();
if (current != null) {
if (current.left != null) {
path.add(0);
newPath(current.left, path,allPaths);
}
if (current.right != null) {
path.add(1);
newPath(current.right, path, allPaths);
}
}
allPaths.add(path);
return allPaths;
}
public ArrayList<ArrayList<Integer>> paths(Node<E> n) {
ArrayList<ArrayList<Integer>> allPaths = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> path = new ArrayList<Integer>();
return newPath(n, path, allPaths);
}
Это правильный путь? У меня возникли проблемы с пониманием того, как использовать рекурсию на бинарных деревьях для подобных вещей.
И как мне это проверить? Я знаю, как создавать и добавлять в двоичное дерево поиска, но когда дело доходит до двоичного дерева, я полностью теряюсь.
Спасибо за любой совет, который вы можете дать, и, если есть что-то, что я могу сделать, чтобы улучшить этот вопрос, пожалуйста, дайте мне знать. Я не задавал много вопросов о переполнении стека.