树遍历结果列表

Question

我研究过树遍历方法，但大多数方法都使用 void 修饰符并且只是打印遍历序列。相反，有没有办法在 Java 中使用递归来制作序列列表？ 入门代码如下。 由于 preorder 是 List，它应该 return 一个列表，但不允许使用全局变量。然后，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;
    }
}

我可以迭代地做，但我不知道如何递归地做。

Answer 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;
    }
}

使用第二个私有方法

不可否认，这不是最好的解决方案，而是一个简单的工作解决方案。

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> 的数据，您只需在将 root 添加到列表时调用 .getData()。