python 递归遍历树

递归遍历树是指在遍历树的过程中，使用递归算法来实现。递归遍历树的基本思路是：先遍历根节点，再遍历每个子树。

以下是 Python 中递归遍历树的示例代码：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorderTraversal(root: TreeNode) -> List[int]:
    res = []
    def dfs(node):
        if not node:
            return
        res.append(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return res

def inorderTraversal(root: TreeNode) -> List[int]:
    res = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        res.append(node.val)
        dfs(node.right)
    dfs(root)
    return res

def postorderTraversal(root: TreeNode) -> List[int]:
    res = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        dfs(node.right)
        res.append(node.val)
    dfs(root)
    return res

在这个示例代码中，我们定义了一个 TreeNode 类来表示树节点。然后，我们定义了三个遍历函数：preorderTraversal（前序遍历）、inorderTraversal（中序遍历）和 postorderTraversal（后序遍历）。这些函数都接受一个树的根节点作为参数，并返回一个包含所有节点值的列表。

在每个遍历函数中，我们都定义了一个内部递归函数 dfs。该函数在遍历节点时使用递归算法。具体来说，每当我们遍历一个节点时，我们将其值添加到 res 列表中，并递归遍历其左子树和右子树。如果节点为空，则直接返回。

最后，我们调用 dfs 函数来遍历整个树，并返回 res 列表。