编写二叉树的递归遍历算法，实现：给定一颗二叉树的“扩展先序遍历”，创建这课二叉树

二叉树的递归遍历算法有三种：前序遍历、中序遍历和后序遍历。我们先看一下前序遍历的算法实现。

前序遍历算法实现：

1. 访问根节点
2. 递归遍历左子树
3. 递归遍历右子树

下面是前序遍历的递归算法实现：

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

def preorderTraversal(root: TreeNode):
    if not root:
        return
    print(root.val)
    preorderTraversal(root.left)
    preorderTraversal(root.right)

接下来是根据“扩展先序遍历”创建二叉树的算法实现。

“扩展先序遍历”是一种序列化二叉树的方式，它的格式如下：

1. 如果节点存在，则输出节点的值，并将节点入栈
2. 如果节点不存在，则输出“#”
3. 如果节点存在左子树，则将左子树入栈
4. 如果节点存在右子树，则将右子树入栈

下面是根据“扩展先序遍历”创建二叉树的算法实现：

def buildTree(preorder: List[str]) -> TreeNode:
    if not preorder:
        return None
    val = preorder.pop(0)
    if val == "#":
        return None
    root = TreeNode(int(val))
    root.left = buildTree(preorder)
    root.right = buildTree(preorder)
    return root

使用示例：

preorder = ["1", "2", "#", "#", "3", "4", "#", "#", "5", "#", "#"]
root = buildTree(preorder)
preorderTraversal(root) # 输出：1 2 3 4 5