java - 递归前序遍历算法如何返回父级？

Question

public static void preorder(Node root) {
    if(root == null) return;

    root.printValue();
    preorder(root.getLeft());
    preorder(root.getRight());
}

我已经尝试过无数次这个函数，但我仍然无法弄清楚在遍历所有左孩子之后，算法如何回到最近的祖先（父母）。有人可以向我解释一下。

Answer 1

return您的方法末尾有一个隐式void：

public static void preorder(Node root) {
    if(root == null) return;

    root.printValue();
    preorder(root.getLeft());
    preorder(root.getRight());
    return;
}

你总是回到调用你的方法。因此，如果父级的方法调用对子级进行了另一个调用，那么当子级的方法调用返回时，它会返回到父级的方法调用。正确的？

希望这是有道理的。就像 Kon 说的，你应该在纸上运行算法。或者，更好的是，如果您知道如何使用调试器，您可以在调试器中单步调试您的代码，看看它是如何工作的。

Answer 2

当遍历到叶子节点时，它的左右子节点都为NULL。preorder(root.getLeft()) 将传递 NULL 并返回。同样，右边也将返回 NULL。然后堆栈弹出并返回父级。

我认为如果您可以使用堆栈干运行它，那么您将能够更好地理解它，这将是最好的。