我研究過樹遍歷方法，但大多數都使用 void 修飾符并且只列印了遍歷序列。相反，有沒有辦法在 Java 中使用遞回來制作序列串列？啟動代碼如下。由于 preorder 是 List<T>，它應該回傳一個串列，但不允許使用全域變數。那么，preorder 方法中應該有一個串列實體，但是因為它是遞回的，所以串列也會被重復創建。我被困住了。精通演算法和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;
}
}
我可以迭代地做它，但我不知道如何遞回地做。
uj5u.com熱心網友回復：
僅使用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;
}
}
使用第二個私有方法
誠然不是最好的解決方案，而是一個簡單的作業解決方案。
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);
}
}
如果您只需要 a 的資料，則List<T>只需.getData()在添加root到串列時呼叫。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446391.html
下一篇：使用迭代廣度優先搜索求解數獨