数据结构二叉树深度优先遍历

二叉树的深度优先遍历是一种遍历二叉树的方法，它按照根节点、左子树、右子树的顺序进行遍历。深度优先遍历有三种方式：前序遍历、中序遍历和后序遍历。

1. 前序遍历（Preorder Traversal）：先访问根节点，然后递归地遍历左子树和右子树。
2. 中序遍历（Inorder Traversal）：先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。
3. 后序遍历（Postorder Traversal）：先递归地遍历左子树和右子树，最后访问根节点。

下面是三种深度优先遍历的示例代码：

1. 前序遍历：

def preorderTraversal(root):
    if root is None:
        return []
    result = []
    result.append(root.val)
    result.extend(preorderTraversal(root.left))
    result.extend(preorderTraversal(root.right))
    return result

2. 中序遍历：

def inorderTraversal(root):
    if root is None:
        return []
    result = []
    result.extend(inorderTraversal(root.left))
    result.append(root.val)
    result.extend(inorderTraversal(root.right))
    return result

3. 后序遍历：

def postorderTraversal(root):
    if root is None:
        return []
    result = []
    result.extend(postorderTraversal(root.left))
    result.extend(postorderTraversal(root.right))
    result.append(root.val)
    return result