二叉树基础与遍历 - 数据结构与算法-学习笔记-上海佼艾

一、二叉树基础概念

1.1 二叉树的定义

二叉树（Binary Tree）是每个节点最多只有两个子节点（称为左孩子和右孩子）的树形数据结构。二叉树是树形结构中最基本也最常用的一种形式，是理解更复杂树结构（如二叉搜索树、平衡二叉树、红黑树、B树等）的基础。

数学上，二叉树可以递归定义：二叉树要么是空树，要么由一个根节点和两个分别称为左子树和右子树的二叉树组成。这个递归定义构成了后续所有二叉树算法的基础。

1 / \ 2 3 / \ \ 4 5 6

1.2 基本术语

根节点（Root）：树结构中最顶层的节点，一棵树只有一个根节点。
叶子节点（Leaf）：没有任何子节点的节点，也称为终端节点。在上图中节点4、5、6均为叶子节点。
父节点与子节点：如果一个节点有子节点，则该节点称为子节点的父节点，反之称为子节点。
兄弟节点（Sibling）：具有相同父节点的节点互为兄弟。
深度（Depth）：从根节点到当前节点的唯一路径上的边数。根节点深度为0。
高度（Height）：从当前节点到最远叶子节点的路径上的边数。叶子节点高度为0。
层（Level）：从根开始定义，根为第1层，根的子节点为第2层，依此类推。
节点度（Degree）：节点拥有的子树个数。二叉树的节点度最大为2。

深度与高度的区分：深度是从根节点向下数，高度是从叶子节点向上数。一棵只有根节点的树，根节点的深度为0，高度也为0。整棵树的高度等于根节点的高度，也等于最大深度值。

1.3 二叉树的数学性质

二叉树第 i 层最多有 2^i-1 个节点（i ≥ 1）。
高度为 h 的二叉树最多有 2^h+1 - 1 个节点（高度从0计）。
对任意非空二叉树，叶子节点数 = 度为2的节点数 + 1。
具有 n 个节点的完全二叉树深度为 ⌊log₂n⌋ + 1。
对于完全二叉树，按层序编号后，节点 i 的左孩子为 2i，右孩子为 2i+1，父节点为 ⌊i/2⌋。

二、二叉树的表示方法

2.1 链式存储（最常用）

链式存储是二叉树最经典的表示方式。每个节点包含三个部分：数据域、指向左子节点的指针（left）、指向右子节点的指针（right）。

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

# 构建示例二叉树
#     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)

三叉链表：在需要频繁回溯父节点的场景中，可以在节点结构中额外增加一个 parent 指针，指向父节点，这种表示方式称为三叉链表。例如在红黑树的插入和删除操作中，使用三叉链表可以简化向上调整的过程。

2.2 数组存储（适用于完全二叉树）

数组存储利用二叉树节点编号与数组下标的对应关系。对于完全二叉树，这种存储方式空间利用率高且访问效率好。

# 数组表示完全二叉树
# 节点 i 的左孩子下标: 2*i + 1
# 节点 i 的右孩子下标: 2*i + 2
# 节点 i 的父节点下标: (i-1) // 2

# 示例: 完全二叉树 [1, 2, 3, 4, 5, 6, 7]
#       1
#      / \
#     2   3
#    / \ / \
#   4  5 6  7
tree = [1, 2, 3, 4, 5, 6, 7]

def left_child(index):
    child = 2 * index + 1
    return child if child < len(tree) else -1

def right_child(index):
    child = 2 * index + 2
    return child if child < len(tree) else -1

def parent(index):
    return (index - 1) // 2 if index > 0 else -1

数组存储的局限性：对于退化成链表的斜树，数组存储会浪费大量空间。例如一棵深度为 k 的右斜树，需要 2^k - 1 个数组位置，实际只存储了 k 个节点，空间浪费极大。因此数组存储仅适用于完全二叉树或接近完全二叉树的场景（如堆、线段树）。

三、二叉树的遍历

二叉树的遍历是指按照某种规则访问树中所有节点各一次的过程。根据访问根节点的顺序不同，分为前序、中序、后序三种深度优先遍历（DFS），以及宽度优先的层序遍历（BFS）。

以下列二叉树为例，分别演示四种遍历结果：

1 / \ 2 3 / \ \ 4 5 6

遍历方式	访问顺序	结果	简称
前序遍历	根 → 左子树 → 右子树	1, 2, 4, 5, 3, 6	根左右
中序遍历	左子树 → 根 → 右子树	4, 2, 5, 1, 3, 6	左根右
后序遍历	左子树 → 右子树 → 根	4, 5, 2, 6, 3, 1	左右根
层序遍历	逐层从左到右	1, 2, 3, 4, 5, 6	BFS

3.1 前序遍历（Preorder Traversal）

前序遍历首先访问根节点，然后递归遍历左子树，最后递归遍历右子树。这种遍历方式在复制一棵树或输出树的结构化表示时非常有用。

# 前序遍历 - 递归实现
def preorder_recursive(root):
    result = []
    def dfs(node):
        if not node:
            return
        result.append(node.val)   # 根
        dfs(node.left)            # 左
        dfs(node.right)           # 右
    dfs(root)
    return result

# 前序遍历 - 迭代实现（显式栈）
def preorder_iterative(root):
    if not root:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        # 注意：栈是后进先出，先压右子树再压左子树
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

3.2 中序遍历（Inorder Traversal）

中序遍历先递归遍历左子树，然后访问根节点，最后递归遍历右子树。二叉搜索树的中序遍历结果是一个递增的有序序列，这是中序遍历最重要的性质。

# 中序遍历 - 递归实现
def inorder_recursive(root):
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)            # 左
        result.append(node.val)   # 根
        dfs(node.right)           # 右
    dfs(root)
    return result

# 中序遍历 - 迭代实现
def inorder_iterative(root):
    result, stack = [], []
    curr = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left      # 一路向左
        curr = stack.pop()
        result.append(curr.val)   # 访问节点
        curr = curr.right         # 转向右子树
    return result

3.3 后序遍历（Postorder Traversal）

后序遍历先递归遍历左子树，然后递归遍历右子树，最后访问根节点。后序遍历在删除二叉树或计算以节点为根的子树大小时非常有用。

# 后序遍历 - 递归实现
def postorder_recursive(root):
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)            # 左
        dfs(node.right)           # 右
        result.append(node.val)   # 根
    dfs(root)
    return result

# 后序遍历 - 迭代实现（双栈法）
def postorder_iterative(root):
    if not root:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)   # 按根右左的顺序入结果
        if node.left:            # 先压左，再压右
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]          # 反转得左右根

# 后序遍历 - 迭代实现（单栈标记法）
def postorder_single_stack(root):
    result, stack = [], []
    curr, last_visited = root, None
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack[-1]
        if not curr.right or curr.right == last_visited:
            result.append(curr.val)
            last_visited = curr
            stack.pop()
            curr = None
        else:
            curr = curr.right
    return result

3.4 层序遍历（Level Order Traversal）

层序遍历按从上到下、从左到右的顺序逐层访问节点，本质上是广度优先搜索（BFS）在二叉树上的应用。层序遍历可以方便地求解树宽、判断完全二叉树、进行序列化等。

# 层序遍历 - 队列实现
from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)      # 二维数组，每层一组
    return result

# 示例输出（以上图二叉树为例）
# [[1], [2, 3], [4, 5, 6]]

# 层序遍历 - 简化版（一维输出）
def level_order_flat(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result
# [1, 2, 3, 4, 5, 6]

遍历口诀：前序遍历：根左右；中序遍历：左根右；后序遍历：左右根。牢记这三句话，递归遍历的代码结构就掌握了。三种遍历的区别仅在于 result.append(node.val) 这一行的位置不同。

四、递归与迭代的对比分析

对比维度	递归实现	迭代实现
代码简洁性	非常简洁，与数学定义一致	相对复杂，需要手动管理栈
空间复杂度	O(h)，h为树高（系统调用栈）	O(h)，h为树高（显式栈）
栈溢出风险	树高过大时存在	可控制，通常无溢出
性能开销	函数调用开销大	仅循环操作，效率更高
可读性	优秀，符合递归思维	一般，需理解栈的变化过程

选择建议：面试和工程中，优先使用递归实现，代码简洁且不易出错。当树深度可能超过1000层（Python默认递归深度限制约1000）时，改用迭代实现或设置 sys.setrecursionlimit()。

4.1 递归的深层理解

递归遍历的核心思想是分治法：将二叉树问题分解为"访问根"和"递归处理左右子树"两个子问题。每个子问题的解法和原问题相同，只是规模更小。递归的终止条件是遇到空节点（None），此时直接返回。

递归函数的执行过程可以用调用栈（Call Stack）来理解。每次递归调用都会在系统栈上压入一个新的栈帧，包含局部变量和返回地址。当当前调用返回时，栈帧弹出，程序回到上一层调用点继续执行。

# 理解递归调用栈 - 以前序遍历为例
# 对二叉树 [1, 2, 3] 执行 preorder_recursive(1)
#
# 调用栈变化:
# dfs(1) -> 输出1 -> dfs(2) -> 输出2 -> dfs(None)返回 -> dfs(None)返回
#        -> 回到 dfs(1) -> dfs(3) -> 输出3 -> dfs(None)返回 -> dfs(None)返回
#        -> 回到 dfs(1) -> 结束
#
# 结果: [1, 2, 3]

4.2 迭代的核心思想

迭代遍历本质上是手动模拟递归调用栈的行为。我们使用一个显式的栈来替代系统调用栈。理解迭代遍历的关键在于理解节点的入栈和出栈时机：

前序迭代：访问节点后立即将右孩子和左孩子入栈（注意顺序，右先入左后入以保证左先出）。
中序迭代：用一个指针模拟递归中"一路向左"的行为，弹出时访问节点，然后转向右子树。
后序迭代：最复杂。双栈法利用前序遍历的变形（根右左）再反转得到左右根。单栈法需要一个额外指针记录上次访问的节点来区分右子树是否已处理。

五、Morris遍历 —— 常数空间的遍历算法

Morris遍历由 J. H. Morris 在1979年提出，其核心思想是利用叶子节点的空闲指针（空指针）来建立临时的回溯路径，从而在不使用额外栈或队列的情况下完成树的遍历。Morris遍历的空间复杂度为 O(1)，时间复杂度仍为 O(n)。

Morris遍历的原理：在当前节点的左子树中找到最右节点（即中序遍历的前驱节点），将其右指针指向当前节点，从而建立一条从叶子节点回溯到祖先节点的临时路径。遍历完成后恢复原始树结构。

5.1 Morris中序遍历

# Morris中序遍历 - 空间复杂度 O(1)
def morris_inorder(root):
    result = []
    curr = root
    while curr:
        if not curr.left:
            # 左子树为空，直接访问当前节点
            result.append(curr.val)
            curr = curr.right
        else:
            # 找到当前节点的前驱节点（左子树的最右节点）
            predecessor = curr.left
            while predecessor.right and predecessor.right != curr:
                predecessor = predecessor.right

            if not predecessor.right:
                # 建立线索：前驱节点的右指针指向当前节点
                predecessor.right = curr
                curr = curr.left
            else:
                # 恢复树结构：断开线索
                predecessor.right = None
                result.append(curr.val)
                curr = curr.right
    return result

5.2 Morris前序遍历

# Morris前序遍历
def morris_preorder(root):
    result = []
    curr = root
    while curr:
        if not curr.left:
            result.append(curr.val)
            curr = curr.right
        else:
            predecessor = curr.left
            while predecessor.right and predecessor.right != curr:
                predecessor = predecessor.right

            if not predecessor.right:
                # 前序在建立线索时访问节点（根之前）
                result.append(curr.val)
                predecessor.right = curr
                curr = curr.left
            else:
                predecessor.right = None
                curr = curr.right
    return result

Morris遍历的优缺点：优点在于空间复杂度仅为 O(1)，适合内存受限的场景（如嵌入式系统、大文件处理）。缺点在于遍历过程中会临时修改树的结构（虽然后续会恢复），不适合并发环境；且代码实现不如递归直观，理解和调试成本较高。在工程实践中，Morris遍历更多地作为一种算法思维的体现，实际应用不如递归和迭代广泛。

六、时间复杂度与空间复杂度分析

遍历方法	时间复杂度	空间复杂度	说明
递归遍历（前/中/后序）	O(n)	O(h)	h 为树高，最坏 O(n)（斜树），平均 O(log n)
迭代遍历（前/中/后序）	O(n)	O(h)	显式栈，空间开销与递归类似但可控
层序遍历（队列）	O(n)	O(w)	w 为最大宽度，最坏 O(n)（完全二叉树底层）
Morris遍历	O(n)	O(1)	常数空间，但每个节点最多被访问两次

时间复杂度分析：每种遍历方法都恰好访问每个节点一次，所以时间复杂度均为 O(n)，其中 n 是二叉树中的节点总数。Morris遍历中每个节点最多被访问两次（一次建立线索，一次访问），因此常数项稍大，但渐近复杂度仍然是 O(n)。

空间复杂度分析：

递归遍历：空间消耗来自系统调用栈的深度，等于递归的深度，即树的高度 h。完全二叉树中 h ≈ log₂n，斜树中 h = n。
迭代遍历：显式栈的最大长度同样和树高成正比，最坏情况 O(n)。
层序遍历：队列的最大长度等于树的最大宽度 w。满二叉树底层宽度为 (n+1)/2，即 O(n)。
Morris遍历：除了结果数组外，仅使用常数个指针变量，空间复杂度 O(1)。

七、基于遍历的经典应用

7.1 二叉树的序列化与反序列化

序列化将二叉树转换为字符串表示，以便于存储和传输；反序列化则从字符串重建二叉树。前序遍历+标记空节点是最常用的序列化方案。

# 二叉树的序列化 - 前序遍历实现
def serialize(root):
    def dfs(node, sb):
        if not node:
            sb.append("None")
            return
        sb.append(str(node.val))
        dfs(node.left, sb)
        dfs(node.right, sb)
    result = []
    dfs(root, result)
    return ",".join(result)

# 反序列化
def deserialize(data):
    def dfs(it):
        val = next(it)
        if val == "None":
            return None
        node = TreeNode(int(val))
        node.left = dfs(it)
        node.right = dfs(it)
        return node
    return dfs(iter(data.split(",")))

7.2 求二叉树的最大深度

# 递归法 - 后序遍历思想
def max_depth(root):
    if not root:
        return 0
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    return max(left_depth, right_depth) + 1

# 迭代法 - 层序遍历思想
def max_depth_bfs(root):
    if not root:
        return 0
    depth, queue = 0, deque([root])
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

7.3 判断平衡二叉树

# 判断平衡二叉树 - 后序遍历 + 提前剪枝
def is_balanced(root):
    def check(node):
        if not node:
            return 0
        left = check(node.left)
        if left == -1:
            return -1
        right = check(node.right)
        if right == -1:
            return -1
        if abs(left - right) > 1:
            return -1
        return max(left, right) + 1
    return check(root) != -1

7.4 从前序与中序遍历序列构造二叉树

# 经典面试题：从前序和中序遍历重建二叉树
def build_tree(preorder, inorder):
    if not preorder or not inorder:
        return None

    # 前序第一个节点为根
    root_val = preorder[0]
    root = TreeNode(root_val)

    # 在中序中找到根的位置
    root_idx = inorder.index(root_val)

    # 递归构建左右子树
    root.left = build_tree(preorder[1:1 + root_idx],
                          inorder[:root_idx])
    root.right = build_tree(preorder[1 + root_idx:],
                           inorder[root_idx + 1:])
    return root

7.5 判断对称二叉树

# 判断二叉树是否对称（镜像对称）
def is_symmetric(root):
    def check(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val and
                check(left.left, right.right) and
                check(left.right, right.left))
    return check(root.left, root.right) if root else True

# 层序判断法
def is_symmetric_bfs(root):
    if not root:
        return True
    queue = deque([root.left, root.right])
    while queue:
        t1 = queue.popleft()
        t2 = queue.popleft()
        if not t1 and not t2:
            continue
        if not t1 or not t2:
            return False
        if t1.val != t2.val:
            return False
        queue.append(t1.left)
        queue.append(t2.right)
        queue.append(t1.right)
        queue.append(t2.left)
    return True

八、二叉树的常见类别

类别	定义	特点	应用
满二叉树（Full Binary Tree）	每个节点要么是叶子，要么有两个子节点	没有度为1的节点	表达式树、霍夫曼树
完全二叉树（Complete Binary Tree）	除最后一层外每层满，最后一层节点靠左排列	可用数组高效存储，节点编号满足 2i 和 2i+1	堆（Heap）、线段树
完美二叉树（Perfect Binary Tree）	所有叶子在同一层，所有内部节点度均为2	节点数 = 2^h+1 - 1，最对称的二叉树	理论分析中的最优情况
平衡二叉树（Balanced Binary Tree）	任意节点的左右子树高度差不超过1	AVL树、红黑树均为平衡二叉树的变种	高效查找、数据库索引
二叉搜索树（BST）	左子树所有节点 < 根 < 右子树所有节点	中序遍历为升序序列，支持 O(h) 的查找	有序数据存储、查找表

完美二叉树（高度h=2，节点数=7）: 1 / \ 2 3 / \ / \ 4 5 6 7 完全二叉树（非完美）: 1 / \ 2 3 / \ 4 5 满二叉树（非完全）: 1 / \ 2 3 / \ 4 5 斜树（最不平衡）: 1 \ 2 \ 3

类别关系：完美二叉树一定是完全二叉树和满二叉树，但反之不成立。完全二叉树不一定是满二叉树（可以有度为1的节点，且必须靠左）。满二叉树也不一定是完全二叉树（节点可以靠右）。平衡二叉树关注的是树的高度平衡性，与节点填充方式无关。

九、核心要点总结

一、二叉树基础

二叉树是每个节点最多有两个子节点的树形结构。关键术语包括根节点、叶子节点、深度（从根向下）、高度（从叶向上）。二叉树具有丰富的数学性质，如层节点数最大值、总节点数最大值、叶子与度为2节点的关系等。

二、二叉树的表示

链式存储使用节点类（val, left, right），是通用表示法。数组存储利用完全二叉树的编号规律（左孩子2i+1，右孩子2i+2），空间效率高但仅适用于完全二叉树。三叉链表增加parent指针，便于回溯。

三、四种遍历方式

前序（根左右）、中序（左根右）、后序（左右根）、层序（BFS）。前序常用于序列化和树结构复制；中序在BST中产生有序序列；后序用于树删除和子树计算；层序用于求宽度和层级相关的问题。

四、递归与迭代

递归代码简洁但受系统栈深度限制。迭代使用显式栈模拟递归过程，更可控但代码复杂。前序迭代最简单（根先入栈，右左入栈），中序迭代需"一路向左"后再弹出，后序迭代最复杂（双栈或标记法）。

五、Morris遍历

利用叶子节点的空闲指针建立临时回溯路径，实现O(1)空间复杂度的遍历。核心操作是寻找前驱节点并建立/断开线索。中序和前序的Morris实现相对简单，后序的Morris实现较复杂。适合内存受限场景。

六、复杂度总结

所有遍历方法时间复杂度均为O(n)。递归和迭代的空间复杂度为O(h)，层序为O(w)，Morris为O(1)。n为节点数，h为树高，w为最大宽度。斜树下h=O(n)，完全二叉树下h=O(log n)。

七、经典应用

遍历思想广泛应用于二叉树相关问题：序列化/反序列化（前序+None标记）、求最大深度（后序或层序）、判断平衡二叉树（后序+剪枝）、从前序中序重建二叉树、判断对称二叉树（递归检查镜像位置）、BST验证（中序单调递增）等。

八、二叉树类别

满二叉树（无一度节点）、完全二叉树（末层靠左排列）、完美二叉树（全满最对称）、平衡二叉树（高度平衡）、二叉搜索树（有序中序）。理解这些类别及其关系，有助于选择合适的树结构解决实际问题。

十、进一步思考与实践

掌握了二叉树的基础遍历之后，可以进一步探索以下进阶主题：

二叉搜索树（BST）：利用中序遍历的有序性，实现高效的插入、删除和查找操作。BST的删除操作（找后继节点替换）是经典考题。
平衡二叉树（AVL）：在BST基础上增加平衡因子约束，通过旋转操作（左旋、右旋、左右旋、右左旋）维持树的高度平衡，确保 O(log n) 的操作复杂度。
红黑树：相对宽松的平衡条件（5条性质），减少旋转次数，是工程中最常用的平衡树结构（如 TreeMap、std::map）。
线段树与树状数组：利用完全二叉树的数组存储特性，实现高效的范围查询与更新。
二叉树在表达式求值中的应用：使用后序遍历计算表达式树的值，是编译原理中语法分析的基础。

练习建议：在 LeetCode 上系统地练习二叉树题目，推荐按以下顺序：先做 144（前序）、94（中序）、145（后序）、102（层序）四道遍历基础题，然后做 104（最大深度）、110（平衡二叉树）、101（对称二叉树）、105（重建二叉树）、297（序列化），最后挑战 124（二叉树最大路径和）和 236（最近公共祖先）等进阶题目。遍历是二叉树所有问题的基础，熟练掌握遍历就等于掌握了解决二叉树问题的钥匙。