return 语句在递归函数中究竟是如何工作的？

Question

我很难解决任何二叉树问题，而且大多数问题都是递归的，所以我决定绕道而行，重新从基础开始。这基本上是预序遍历列表。如果至少有 1 个节点，我已经确定了两种可以给我正确结果的方法，但我不确定这两者之间的内在差异。可以看到，一个return遇到null时是列表，另一个return遇到null时是null:

public List<Integer> getList1(TreeNode root) {
    return getList1Helper(root, new ArrayList<>());
}

private List<Integer> getList1Helper(TreeNode root, List<Integer> list) {
    if (root == null) {
        return list;
    }
    list.add(root.val);
    getList1Helper(root.left, list);
    getList1Helper(root.right, list);
    return list;
}

public List<Integer> getList2(TreeNode root) {
    return getList2Helper(root, new ArrayList<>());
}

private List<Integer> getList2Helper(TreeNode root, List<Integer> list) {
    if (root == null) {
        return null; // difference denoted *
    }
    list.add(root.val);
    getList2Helper(root.left, list);
    getList2Helper(root.right, list);
    return list;
}

有人对此有什么想法吗？另外，为什么函数 return 没有列表并在遇到第一个 null 时停止所有递归？

Answer 1

在辅助函数中 return 什么并不重要，因为您从不使用 returned 值。您也可以将方法定义为 void 并仍然得到正确的结果。
本质上你正在做的（正确的）只是传递列表的引用。

对于你的第二个问题：假设你在二叉树中找到了一个向下三层的空节点。当您 return 在该级别时，您将 return 到该二叉树中的第二级，那里还有其他 getListHelper-calls 等待发生。只有当每个节点都被访问过时，first getListHelper 才会调用 return 列表到 getList 方法。

Answer 2

虽然您 return 在两个版本的代码中有所不同，但两个辅助函数实际上使用来自递归调用的值 return：

getList2Helper(root.left, list);

上面进行了递归调用，return有些东西，但是调用者没有对它做任何事情。

唯一一次 returned 值有差异，是在基本情况开始时。这意味着 initial 有差异当调用者将 null 作为第一个参数传递时（表示一棵空树）。第一个版本将 return 一个空数组列表，而第二个版本将 return null。所以它们并不完全等价。 return 数组列表的那个将更多是我期望得到的空树（即空数组列表，而不是 null）。

正在清理

由于辅助函数实际上填充了作为参数给出的数组列表，因此它不需要 return 任何东西。主函数可以创建数组列表，将其传递给助手（return 什么都没有），然后 return 填充列表。

像这样：

public List<Integer> getList(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    getListHelper(root, list);
    return list;
}

private void getListHelper(TreeNode root, List<Integer> list) {
    if (root == null) {
        return;
    }
    list.add(root.val);
    getListHelper(root.left, list);
    getListHelper(root.right, list);
}

备选

您可以完全避免使用辅助函数（带有第二个参数），而是从递归调用的列表中填充本地数组列表 return:

public List<Integer> getList(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root != null) {
        list.add(root.val);
        list.addAll(getList(root.left));
        list.addAll(getList(root.right));
    }
    return list;
}

这样效率较低，因为值会多次从一个列表复制到另一个列表。使用允许在 O(1) 时间内连接列表的链表实现，您可以克服这个缺点。

return 语句在递归函数中究竟是如何工作的？

How exactly does return statement work in recursive function?

java

binary-tree

preorder

正在清理

备选