有人能解释二叉树递归的顺序遍历吗？

Question

我有一些递归遍历二叉树的代码。

def IN_DFS(node, result=None):
    if result is None:
        result = []
    if not node:
        return result
    Solution.IN_DFS(node.left, result)

    result.append(node.val)

    Solution.IN_DFS(node.right, result)

    return result

我需要一些帮助来了解正在发生的事情。我了解递归，我知道如何以迭代的顺序遍历二叉树，但似乎看不到这个递归解决方案的效果。

因此，如果'节点'不是无，我们将调用node.left递归函数，直到我们到达一个前导节点，在这种情况下node.left是无，然后我们移动到下一行'result.append（node.val)'? - 这对吗？

然后在“节点”上调用递归函数。对吧?？

假设我们到达第一个node.left叶节点，将其值添加到“结果”，然后返回一步到其父节点，将其值添加到“结果”，然后检查其正确的子节点？

我不认为上面的说法是对的——有人能帮忙吗？谢谢

Answer 1

>

假设我们到达第一个节点。左叶节点，将其值添加到“结果”，然后返回到其父级，将其值添加到“结果”，然后检查其右子级？否，移动到右侧子树（当前节点的右侧节点）