递归先序遍历算法如何回到父节点？

Question

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

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

我试过多次去理解这个函数，但是我仍然无法理解在遍历所有左子节点之后，算法如何返回到最近的祖先（父节点）。有人能解释一下吗？

- cantfindaname88

---

学习的方法是拿出一张纸，画一个简单的树形图，然后逐步运行算法。 - Kon

使用一张纸确实帮助我得出了结论。我的第一个方法是使用堆栈实现。然后我逐步跟踪递归调用，并意识到它们也像堆栈一样运作。谢谢大家。 - cantfindaname88

Answer 1

你的void方法结尾有一个隐式的return：

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

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

当你调用某个方法时，总是会返回到调用该方法的方法中。因此，如果父级方法的调用又为子级方法调用，那么当子级方法调用返回时，它会返回到父级方法中。没错吧？

希望这样讲明白了。就像Kon所说，你应该在纸上运行算法。或者，更好的方法是，如果你知道如何使用调试器，你可以在调试器中逐步执行代码，看看它是如何工作的。

- DaoWen

Answer 2

当遍历到叶子节点时，它的左右孩子将是NULL。然后，preorder（root.getLeft（））将传递NULL并返回。同样地，右侧也会返回NULL。然后，堆栈弹出并返回父节点。

我认为最好使用堆栈进行干燥运行，然后您将能够更好地理解它。

- gusaki