Результат обхода дерева в виде списка
Я изучил методы обхода дерева, но большинство из них используют модификаторы void и просто печатают последовательность обхода. Вместо этого есть ли способ составить список последовательности, используя рекурсию в Java? Стартовый код ниже. Поскольку предварительный заказ — это List<T>, он должен возвращать список, но глобальные переменные не допускаются. Затем в методе предварительного заказа должен быть экземпляр списка, но поскольку он рекурсивный, список также будет создаваться повторно. Я застрял. Может ли кто-нибудь, разбирающийся в алгоритмах и Java, помочь мне с этим?
public class Traversals<T extends Comparable<? super T>> {
//no global variables allowed
public List<T> preorder(TreeNode<T> root) {
// CODE HERE.
}
}
public class TreeNode<T extends Comparable<? super T>> {
private T data;
private TreeNode<T> left;
private TreeNode<T> right;
TreeNode(T data) {
this.data = data;
}
T getData() {
return data;
}
TreeNode<T> getLeft() {
return left;
}
TreeNode<T> getRight() {
return right;
}
void setData(T data) {
this.data = data;
}
void setLeft(TreeNode<T> left) {
this.left = left;
}
void setRight(TreeNode<T> right) {
this.right = right;
}
}
я мог бы сделать это итеративно, но я не знаю, как это сделать рекурсивно.
Ответы 1
Используя только метод preorder(TreeNode<T>)
Это также должно работать и удовлетворять всем вашим ограничениям. Каждый раз создается новый список пустой список и пополняется списком из левой и правой ветвей рекурсии.
public class Traversals<T extends Comparable<? super T>> {
//no global variables allowed
public List<TreeNode<T>> preorder(TreeNode<T> root) {
var preorderLst = new LinkedList<TreeNode<T>>();
if (root != null) {
preorderLst.add(root);
var leftList = preorder(root.getLeft());
var rightList = preorder(root.getRight());
preorderLst.addAll(leftList);
preorderLst.addAll(rightList);
}
return preorderLst;
}
}
Использование 2-го частного метода
По общему признанию, не самое красивое решение, но простое рабочее решение.
public class Traversals<T extends Comparable<? super T>> {
//no global variables allowed
public List<TreeNode<T>> preorder(TreeNode<T> root) {
var preorderLst = new LinkedList<TreeNode<T>>();
preorder(root, preorderLst);
return preorderLst;
}
private void preorder(TreeNode<T> root, List<TreeNode<T>> preorderLst){
if (root == null) return;
preorderLst.add(root);
preorder(root.getLeft(), preorderLst);
preorder(root.getRight(), preorderLst);
}
}
Если вам просто нужны данные для List<T>, вам просто нужно вызвать .getData() при добавлении root в список.
Спасибо за ваш вклад. Я пытался сделать что-то похожее на ваше. Проблема в том, что каждый добавляемый код должен находиться в публичном List<TreeNode<T>> preorder(TreeNode<T> root), а не путем создания другого метода (preorder). Вот почему я застрял... Не могли бы вы предложить решение? Может быть, я новичок, поэтому я неправильно понимаю вопрос.
Это, безусловно, шоу-стоп :D Поскольку итеративный подход также не разрешен, у меня сейчас нет идеи для вас.
Есть решение, я думаю. Пожалуйста, отметьте это как принятый ответ, если это сработало для вас :)
Спасибо за ваши ответы. Приму ваш ответ.
preorder()?