二叉树深度遍历（前/中/后 * 递归/迭代 6种实现结果）python

二叉树的深度优先遍历（Depth First Search, DFS），主要有三种策略：前序遍历、中序遍历和后序遍历。在Python中，可以分别通过递归和迭代的方式实现这六种组合：

1. **前序遍历（递归）**:

def dfs_preorder(root):
    if root is not None:
        print(root.val)
        dfs_preorder(root.left)
        dfs_preorder(root.right)

2. **前序遍历（迭代）**:

def dfs_preorder_iterative(root):
    stack, output = [root], []
    while stack:
        node = stack.pop()
        if node:
            output.append(node.val)
            stack.extend([node.right, node.left])
    return output

3. **中序遍历（递归）**:

def dfs_inorder(root):
    if root is not None:
        dfs_inorder(root.left)
        print(root.val)
        dfs_inorder(root.right)

4. **中序遍历（迭代）**:

def dfs_inorder_iterative(root):
    stack, output = [], []
    curr = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        output.append(curr.val)
        curr = curr.right
    return output

5. **后序遍历（递归）**:

def dfs_postorder(root):
    if root is not None:
        dfs_postorder(root.left)
        dfs_postorder(root.right)
        print(root.val)

6. **后序遍历（迭代）**:

def dfs_postorder_iterative(root):
    stack, output = [root], []
    while stack:
        node = stack.pop()
        if node.left is None and node.right is None:
            output.insert(0, node.val)
        else:
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
    return output