042. 编写一个函数，实现二叉树的前序、中序、后序遍历

在 Python 中，可以通过递归或迭代的方式实现二叉树的前序、中序和后序遍历。

定义二叉树节点类

class TreeNode:
    """
    定义二叉树的节点类。
    """
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

实现遍历函数

def preorder_traversal(root):
    """
    前序遍历二叉树。

    参数:
        root (TreeNode): 二叉树的根节点。

    返回:
        list: 前序遍历的结果。
    """
    result = []

    def dfs(node):
        if not node:
            return
        result.append(node.value)  # 访问根节点
        dfs(node.left)  # 遍历左子树
        dfs(node.right)  # 遍历右子树

    dfs(root)
    return result

def inorder_traversal(root):
    """
    中序遍历二叉树。

    参数:
        root (TreeNode): 二叉树的根节点。

    返回:
        list: 中序遍历的结果。
    """
    result = []

    def dfs(node):
        if not node:
            return
        dfs(node.left)  # 遍历左子树
        result.append(node.value)  # 访问根节点
        dfs(node.right)  # 遍历右子树

    dfs(root)
    return result

def postorder_traversal(root):
    """
    后序遍历二叉树。

    参数:
        root (TreeNode): 二叉树的根节点。

    返回:
        list: 后序遍历的结果。
    """
    result = []

    def dfs(node):
        if not node:
            return
        dfs(node.left)  # 遍历左子树
        dfs(node.right)  # 遍历右子树
        result.append(node.value)  # 访问根节点

    dfs(root)
    return result

测试代码

# 创建一个二叉树
#       1
#      / \
#     2   3
#    / \   \
#   4   5   6
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

# 前序遍历
print("前序遍历结果：", preorder_traversal(root))  # 输出：[1, 2, 4, 5, 3, 6]

# 中序遍历
print("中序遍历结果：", inorder_traversal(root))  # 输出：[4, 2, 5, 1, 3, 6]

# 后序遍历
print("后序遍历结果：", postorder_traversal(root))  # 输出：[4, 5, 2, 6, 3, 1]

代码解释

1. 前序遍历：访问根节点，然后递归遍历左子树，最后递归遍历右子树。
2. 中序遍历：递归遍历左子树，访问根节点，然后递归遍历右子树。
3. 后序遍历：递归遍历左子树，递归遍历右子树，最后访问根节点。

运行结果

运行上述代码后，输出如下：

前序遍历结果： [1, 2, 4, 5, 3, 6]
中序遍历结果： [4, 2, 5, 1, 3, 6]
后序遍历结果： [4, 5, 2, 6, 3, 1]

注意事项

递归方法：递归方法简洁且易于理解，但可能会导致栈溢出，尤其是在树非常深的情况下。

迭代方法：也可以通过使用栈来实现迭代方法，避免递归调用的开销。迭代方法在处理大规模数据时更为高效。

适用场景：

• 前序遍历适用于需要先访问根节点的场景。

• 中序遍历适用于需要按顺序访问节点的场景，例如二叉搜索树的中序遍历结果是有序的。

• 后序遍历适用于需要先访问子节点的场景，例如计算表达式树的值。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)