二叉树遍历算法详解：掌握二叉树遍历的精髓，解锁数据结构奥秘

# 1. 二叉树基础

二叉树是一种非线性数据结构，由一个根节点和零个或多个子树组成。每个子树也是一棵二叉树，并且每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的遍历是指访问树中每个节点的过程。遍历算法有多种，包括深度优先遍历和广度优先遍历。深度优先遍历沿着树的深度优先搜索，而广度优先遍历沿着树的宽度优先搜索。

# 2.1 深度优先遍历

深度优先遍历（DFS）是一种遍历二叉树的递归算法，它沿着一条路径向下遍历，直到到达叶节点，然后回溯并沿着另一条路径继续遍历。DFS 有三种主要类型：前序遍历、中序遍历和后序遍历。

### 2.1.1 前序遍历

前序遍历以根节点开始，然后依次遍历左子树和右子树。它遵循以下顺序：

根节点 -> 左子树 -> 右子树

**代码块：**

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

    参数：
        root: 二叉树的根节点

    返回：
        遍历结果列表
    """
    if root is None:
        return []

    result = [root.val]
    result.extend(preorder_traversal(root.left))
    result.extend(preorder_traversal(root.right))

    return result

**逻辑分析：**

* 如果根节点为空，则返回空列表。
* 将根节点的值添加到结果列表中。
* 递归遍历左子树，并将结果添加到结果列表中。
* 递归遍历右子树，并将结果添加到结果列表中。
* 返回结果列表。

### 2.1.2 中序遍历

中序遍历以左子树开始，然后是根节点，最后是右子树。它遵循以下顺序：

左子树 -> 根节点 -> 右子树

**代码块：**

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

    参数：
        root: 二叉树的根节点

    返回：
        遍历结果列表
    """
    if root is None:
        return []

    result = []
    result.extend(inorder_traversal(root.left))
    result.append(root.val)
    result.extend(inorder_traversal(root.right))

    return result

**逻辑分析：**

* 如果根节点为空，则返回空列表。
* 递归遍历左子树，并将结果添加到结果列表中。
* 将根节点的值添加到结果列表中。
* 递归遍历右子树，并将结果添加到结果列表中。
* 返回结果列表。

### 2.1.3 后序遍历

后序遍历以左子树和右子树开始，然后是根节点。它遵循以下顺序：

左子树 -> 右子树 -> 根节点

**代码块：**

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

    参数：
        root: 二叉树的根节点

    返回：
        遍历结果列表
    """
    if root is None:
        return []

    result = []
    result.extend(postorder_traversal(root.left))
    result.extend(postorder_traversal(root.right))
    result.append(root.val)

    return result

**逻辑分析：**

* 如果根节点为空，则返回空列表。
* 递归遍历左子树，并将结果添加到结果列表中。
* 递归遍历右子树，并将结果添