树与二叉树

第 7 章 · 数据结构与算法

一、树的基本概念

树是由 n（n≥0）个节点组成的有限集合。当 n=0 时称为空树；当 n>0 时，有且仅有一个节点称为根（root），其余节点可分为若干互不相交的子树，每棵子树本身又是一棵树。树是递归定义的：每个节点可以有零个或多个子节点（children），除根外每个节点有且仅有一个父节点（parent）。同一父节点下的子节点互为兄弟（siblings）。没有子节点的节点称为叶节点（leaf）。

度：节点的度指其子节点个数；树的度指所有节点中度的最大值。深度（depth）：从根到该节点所经的边数，根的深度为 0。高度（height）：从该节点到最远叶子的边数，叶子的高度为 0；有时也把「根到叶的最大节点数」叫高度，二者差 1，使用时需统一。树的层（level）：根为第 0 层或第 1 层（教材不一），其子为下一层，依此类推。

二、二叉树

二叉树（binary tree）是每个节点最多有两个子节点的树，通常称为左子（left child）和右子（right child）。即使只有一个子节点，也要区分是左还是右，因此二叉树是有序的。空树也是一棵二叉树。

满二叉树：每一层的节点数都达到该层最大数（即第 i 层有 2^i 个节点）。完全二叉树：除最后一层外其余层都是满的，且最后一层从左到右连续排满（或仅缺右侧若干节点）。完全二叉树适合用数组存储：根在下标 0，节点 i 的左子为 2i+1、右子为 2i+2、父为 (i-1)//2。

2.1 顺序存储与链式存储

链式存储：每个节点是一个结构体，包含值 val 以及指针 left、right 指向左右子节点；根节点由单独指针维护。这是最常用的实现方式，便于动态增删和递归遍历。顺序存储：用数组按层序存放：下标 0 为根，节点 i 的左子下标 2i+1、右子 2i+2、父 (i-1)//2。完全二叉树用数组可节省指针空间；非完全二叉树用数组会浪费空位。

完全二叉树数组存储示例：根在 arr[0]，节点下标 i 的左子为 arr[2*i+1]、右子为 arr[2*i+2]、父为 arr[(i-1)//2]。层序遍历顺序即数组下标顺序。

from typing import List, Optional

def left_child_idx(i: int) -> int:
    """完全二叉树：节点 i 的左子下标。"""
    return 2 * i + 1

def right_child_idx(i: int) -> int:
    return 2 * i + 2

def parent_idx(i: int) -> int:
    """节点 i 的父下标；根 0 的父可视为 -1。"""
    return (i - 1) // 2

def level_order_array(arr: List[int], n: int) -> List[int]:
    """完全二叉树用数组 arr（长度至少 n）的层序即 arr[0..n-1]。"""
    return arr[:n]

三、二叉树的遍历

遍历即按某种规则访问树中每个节点恰好一次。深度优先（DFS）按「根与左右子」的访问顺序分为三种：

• 前序（preorder）：先访问根，再递归前序遍历左子树，再递归前序遍历右子树。顺序：根 → 左子树 → 右子树。
• 中序（inorder）：先递归中序遍历左子树，再访问根，再递归中序遍历右子树。顺序：左子树 → 根 → 右子树。对二叉搜索树中序得到有序序列。
• 后序（postorder）：先递归后序遍历左子树，再递归后序遍历右子树，最后访问根。顺序：左子树 → 右子树 → 根。常用于「先处理子再处理根」的场景（如释放子树、计算子树信息）。

层序（level order）：按层从上到下、每层从左到右访问。用队列实现：先入根，每次出队一个节点并访问，再将其非空左右子入队，直到队列为空。

四、代码实现：TreeNode 与遍历

下面给出链式二叉树的节点定义，以及递归与迭代（栈/队列）的遍历实现，均返回访问顺序的列表（Python3 + 类型标注）。

4.1 节点定义与递归遍历

from typing import List, Optional

class TreeNode:
    """二叉树节点：val、左子 left、右子 right。"""
    def __init__(
        self,
        val: int,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right

def preorder_rec(root: Optional[TreeNode]) -> List[int]:
    """前序遍历（递归）：根 → 左 → 右。"""
    if root is None:
        return []
    return [root.val] + preorder_rec(root.left) + preorder_rec(root.right)

def inorder_rec(root: Optional[TreeNode]) -> List[int]:
    """中序遍历（递归）：左 → 根 → 右。"""
    if root is None:
        return []
    return inorder_rec(root.left) + [root.val] + inorder_rec(root.right)

def postorder_rec(root: Optional[TreeNode]) -> List[int]:
    """后序遍历（递归）：左 → 右 → 根。"""
    if root is None:
        return []
    return postorder_rec(root.left) + postorder_rec(root.right) + [root.val]

4.2 迭代实现：栈模拟前/中/后序

递归本质是系统栈；用显式栈可改写为迭代。前序：先压根，每次弹出一个节点并访问，再先压右子、再压左子（这样出栈顺序为根→左→右）。中序：从根一路向左压栈，弹出一个并访问，再以其右子为当前根继续「一路向左」。后序：可用「根右左」迭代再反转结果，或双栈/标记法。

from typing import List, Optional

def preorder_iter(root: Optional[TreeNode]) -> List[int]:
    """前序迭代：栈，先压右再压左，出栈即根左右。"""
    out: List[int] = []
    stack: List[TreeNode] = []
    if root is not None:
        stack.append(root)
    while stack:
        node: TreeNode = stack.pop()
        out.append(node.val)
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)
    return out

def inorder_iter(root: Optional[TreeNode]) -> List[int]:
    """中序迭代：一路向左压栈，弹出一个访问，再转右子。"""
    out: List[int] = []
    stack: List[TreeNode] = []
    cur: Optional[TreeNode] = root
    while cur is not None or stack:
        while cur is not None:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        out.append(cur.val)
        cur = cur.right
    return out

def postorder_iter(root: Optional[TreeNode]) -> List[int]:
    """后序迭代：根右左 用栈得到，再反转即 左右根。"""
    out: List[int] = []
    stack: List[TreeNode] = []
    if root is not None:
        stack.append(root)
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.left is not None:
            stack.append(node.left)
        if node.right is not None:
            stack.append(node.right)
    out.reverse()
    return out

4.3 层序遍历（队列）

层序：根入队；每次出队一个节点并访问，再将其非空左子、右子依次入队。这样同一层的节点会按从左到右依次出队。

from collections import deque
from typing import List, Optional

def level_order(root: Optional[TreeNode]) -> List[int]:
    """层序遍历：队列，出队即访问，左子、右子依次入队。"""
    out: List[int] = []
    q: deque[Optional[TreeNode]] = deque()
    if root is not None:
        q.append(root)
    while q:
        node: Optional[TreeNode] = q.popleft()
        if node is None:
            continue
        out.append(node.val)
        if node.left is not None:
            q.append(node.left)
        if node.right is not None:
            q.append(node.right)
    return out

五、性质与操作复杂度

若二叉树有 n 个节点，则边数为 n-1。满二叉树第 i 层最多 2^i 个节点；高度 h 的满二叉树总节点数 2^(h+1)-1。遍历：每个节点访问一次，时间 O(n)；递归栈或显式栈/队列空间 O(h)（h 为树高，最坏链状 O(n)）。

六、常见应用延伸

二叉树遍历是很多算法的基础：表达式树用中序得到中缀表达式、后序可用来求值；二叉搜索树中序得到有序序列；判断对称、求深度、路径和等都可结合递归遍历。层序遍历常用于「按层处理」、求层宽、最短路径（未加权）等。

七、例题与代码详解

以下三道题给出完整题目描述、Python3 解法（带类型标注）与详细讲解。

from typing import Optional

def max_depth(root: Optional[TreeNode]) -> int:
    """递归：空树深度 0；否则 1 + max(左深度, 右深度)。"""
    if root is None:
        return 0
    left_h: int = max_depth(root.left)
    right_h: int = max_depth(root.right)
    return 1 + max(left_h, right_h)

from typing import Optional

def is_symmetric(root: Optional[TreeNode]) -> bool:
    """根为空则对称；否则判断左右子树是否镜像。"""
    if root is None:
        return True
    return _mirror(root.left, root.right)

def _mirror(a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:
    """两棵树镜像：都空则 True；一空一非空 False；
    值相等且 a.left 与 b.right 镜像、a.right 与 b.left 镜像。"""
    if a is None and b is None:
        return True
    if a is None or b is None:
        return False
    if a.val != b.val:
        return False
    return _mirror(a.left, b.right) and _mirror(a.right, b.left)

from typing import Optional

def has_path_sum(root: Optional[TreeNode], target_sum: int) -> bool:
    """递归：到当前节点时，剩余需要凑的值为 target_sum - 当前值；
    若当前为叶且剩余为 0 则 True；否则看左或右是否存在路径。"""
    if root is None:
        return False
    rest: int = target_sum - root.val
    if root.left is None and root.right is None:
        return rest == 0
    return has_path_sum(root.left, rest) or has_path_sum(root.right, rest)

from typing import Optional

def invert_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    """后序（或前序）：先递归翻转左右子树，再交换根的 left/right。"""
    if root is None:
        return None
    invert_tree(root.left)
    invert_tree(root.right)
    root.left, root.right = root.right, root.left
    return root

八、小结

树是层次结构，有根、父、子、兄弟、叶等概念；二叉树每个节点最多两个子（左、右），可顺序存储（完全二叉树）或链式存储（TreeNode + left/right）。遍历分前序（根左右）、中序（左根右）、后序（左右根）与层序（队列）；递归与栈/队列实现各有用处。最大深度、对称性、路径和等经典问题都可归结为递归遍历。下一章会学二叉搜索树与平衡树，在二叉树基础上加上「左小右大」与平衡约束。