Java:二叉树+预序遍历+递归+返回结果列表

Question

关于二进制树的预序遍历的小Java问题，使用递归，并返回所有元素的结果列表。

在网络上，我们可以看到使用递归遍历树的许多结果。然而，他们都"；只打印"；节点，不返回任何内容：

https://makeinjava.com/recursive-binary-tree-traversal-algorithm-java-preorder-postorderinorder/

public static void preOrderRecursive(Node root) {
if (null == root) {
return;
}
System.out.printf("%d ", root.data);
preOrderRecursive(root.left);
preOrderRecursive(root.right);
}

这是一个递归函数，但不返回任何

另一方面，有很多例子表明，它以列表的形式返回二进制树，但使用了一种迭代方式：

public List<Integer> preorderIterative(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.add(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pollLast();
output.add(node.val);
if (node.right != null) {
stack.add(node.right);
}
if (node.left != null) {
stack.add(node.left);
}
}
return output;
}

这是一个迭代函数，它确实以列表的形式返回结果

我的问题是，我很难构建一个递归函数，它以列表的形式返回结果。

我尝试过(但没有成功)：

public static List<Integer> preOrderRecursiveWithReturn(TreeNode root) {
if (null == root) {
return ???;
} else {
return preOrderRecursiveWithReturn(root.left) preOrderRecursiveWithReturn(root.right) ???
}
}

但不幸的是，它不起作用。请帮忙吗？

Answer 1

创建一个将输出列表作为额外参数的辅助函数：

// Helper
private static void preOrderRecursive(Node root, LinkedList<Integer> output) {
if (null == root) {
return;
}
output.add(root.data);
preOrderRecursive(root.left, output);
preOrderRecursive(root.right, output);
}
// Actual function that returns the list
public static LinkedList<Integer> preOrder(Node root) {
LinkedList<Integer> output = new LinkedList<Integer>();
preOrderRecursive(root, output);
return output;
}

Answer 2

另一种选择是不让递归方法返回列表，而是让递归方法添加到列表字段中。

private List<Integer> output;
public static void preOrderRecursive(Node root) {
if (null == root) {
return;
}
//System.out.printf("%d ", root.data);
list.add(root.data);
preOrderRecursive(root.left);
preOrderRecursive(root.right);

}