二叉树遍历 递归算法

二叉树遍历是指按照某种顺序依次访问二叉树中的所有节点。常见的遍历方式有先序遍历、中序遍历、后序遍历和层序遍历。其中，递归算法是实现二叉树遍历的一种常见方法。

以下是二叉树先序遍历的递归算法示例：

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

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        if not root:
            return res
        res.append(root.val)
        res += self.preorderTraversal(root.left)
        res += self.preorderTraversal(root.right)
        return res

在这个示例中，我们定义了一个`TreeNode`类来表示二叉树的节点，其中包含节点的值`val`、左子树`left`和右子树`right`。我们还定义了一个`Solution`类，其中包含了一个`preorderTraversal`方法，用于实现二叉树的先序遍历。该方法接受一个二叉树的根节点作为参数，并返回一个列表，其中包含了按照先序遍历顺序访问的节点值。

具体实现中，我们首先判断根节点是否为空，如果为空则直接返回空列表。否则，我们将根节点的值加入到结果列表中，并递归遍历左子树和右子树，将它们的遍历结果依次加入到结果列表中。最后返回结果列表即可。