---

如果觉得本文对您有所帮助，请点个赞和关注吧，谢谢！！！你的支持就是我持续更新的最大动力

---

一、基本概念

树是一种递归定义的分层非线性数据结构，在计算机科学中用于高效组织具有层级或嵌套关系的数据（如文件系统、DOM树、表达式解析、路由表等）。

---

1. 节点（Node）—— 结构基石

定义

节点是树的基本组成单位，包含数据域和指针域（指向子节点）。

工程实现模板（Python）

from typing import Optional, List

class TreeNode:
    """
    二叉树节点类
    
    属性:
        val: 节点存储的值（可为任意类型，通常为int/str）
        left: 左子节点引用，默认None
        right: 右子节点引用，默认None
    """
    def __init__(self, val=0, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        return f"TreeNode({self.val})"

设计要点：

• 使用 Optional[TreeNode] 明确子节点可为空。
• 实现 __repr__ 便于调试打印。
• 支持泛型扩展（如需存储对象，可改用 TypeVar）。

---

2. 根节点（Root）—— 唯一起点

数学定义

根节点是树中入度为0的唯一节点（无父节点）。

工程意义

• 所有遍历、搜索、插入、删除操作均以根为入口。
• 若 root is None，则代表空树，应作为边界条件优先处理。

示例：

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
# 此时 root 是整棵树的访问入口

---

3. 父节点（Parent）与子节点（Child）—— 关系建模

定义

• 父节点：直接上层节点，每个节点最多一个父节点（除根）。
• 子节点：直接下层节点，在二叉树中最多两个（左、右）。

工程约束

• 二叉树中左右子节点不可互换，顺序具有语义（如BST中小<大）。
• 指针方向：单向向下（从父指向子），无反向指针（除非特殊设计如线索二叉树）。

---

4. 叶节点（Leaf）—— 终止标识

定义

没有子节点的节点称为叶节点（终端节点）。

判定函数

def is_leaf(node: Optional[TreeNode]) -> bool:
    """判断是否为叶节点"""
    return node is not None and node.left is None and node.right is None

应用场景

• 计算路径和（如LeetCode 112）
• 统计叶子数
• 树高计算终止条件

---

5. 深度（Depth）—— 自顶向下度量

定义

节点深度 = 从根节点到该节点所经过的边数（根深度 = 0）。

递归计算函数

def get_depth(root: Optional[TreeNode], target_val: int) -> int:
    """
    查找特定值节点的深度（若不存在返回-1）
    
    时间复杂度: O(n)
    空间复杂度: O(h)
    """
    def dfs(node, current_depth):
        if not node:
            return -1
        if node.val == target_val:
            return current_depth
        left_depth = dfs(node.left, current_depth + 1)
        if left_depth != -1:
            return left_depth
        return dfs(node.right, current_depth + 1)
    
    return dfs(root, 0)

---

6. 高度（Height）—— 自底向上度量

定义

节点高度 = 从该节点到最远叶节点的最长路径边数（叶节点高度 = 0）。

递归计算（推荐写法）

def get_height(node: Optional[TreeNode]) -> int:
    """
    计算节点高度
    
    公式: height(node) = max(height(left), height(right)) + 1
    边界: height(None) = -1 （或 height(Leaf) = 0）
    
    返回值: 整数高度
    """
    if not node:
        return -1  # 空节点高度为-1，使叶节点高度=0
    left_height = get_height(node.left)
    right_height = get_height(node.right)
    return max(left_height, right_height) + 1

标准约定：空树高度 = -1，单节点树高度 = 0。某些教材定义不同，需注意上下文。

---

二、二叉树 —— 从理论到工程实践

严格定义

二叉树（Binary Tree）是满足以下条件的树结构：

1. 每个节点最多有两个子节点；
2. 子节点区分左（left）和右（right），顺序不可交换；
3. 左右子树本身也是二叉树（递归定义）。

---

数学性质（重要！面试高频）

性质编号	描述	公式/说明
P1	第 i 层最多节点数	2^(i-1) （i ≥ 1）
P2	深度为 k 的二叉树最多节点总数	2^k - 1
P3	叶节点数 = 度为2的节点数 + 1	n0 = n2 + 1
P4	节点总数 n = n0 + n1 + n2	n0:叶, n1:度1, n2:度2
P5	完全二叉树中，节点 i 的左孩子 = 2i，右孩子 = 2i+1（数组索引从1起）	用于堆实现
P6	n 个节点的完全二叉树高度 = ⌊log₂n⌋

推导示例（P3）：
设总边数 E = n - 1（树性质）
又 E = 0·n0 + 1·n1 + 2·n2
⇒ n - 1 = n1 + 2n2
代入 n = n0 + n1 + n2
⇒ n0 + n1 + n2 - 1 = n1 + 2n2
⇒ n0 = n2 + 1

---

工程中常见的二叉树类型

类型	定义	应用场景
满二叉树	除叶节点外，所有节点都有两个子节点	理论模型、性能分析基准
完全二叉树	除最后一层外全满，最后一层节点靠左排列	堆（Heap）、数组存储优化
平衡二叉树	任意节点左右子树高度差 ≤ 1	AVL树、保证O(log n)操作
二叉搜索树(BST)	左子树 < 根 < 右子树（中序遍历有序）	快速查找、范围查询
退化二叉树	每层仅一个节点（形如链表）	最坏情况分析、需避免

---

三、二叉树遍历 —— 四种方式深度剖析

遍历的本质：按特定顺序访问每个节点一次且仅一次

---

（一）深度优先遍历（DFS）—— 递归与迭代双实现

▶ 1. 前序遍历（Pre-order: Root → Left → Right）

递归实现（推荐初学）

def preorder_recursive(root: Optional[TreeNode]) -> List[int]:
    """
    递归前序遍历
    
    执行顺序:
        1. 访问当前节点（追加值）
        2. 递归遍历左子树
        3. 递归遍历右子树
    
    时间复杂度: O(n) — 每个节点访问一次
    空间复杂度: O(h) — 递归栈深度（h=树高）
    """
    if not root:
        return []
    result = [root.val]
    result += preorder_recursive(root.left)
    result += preorder_recursive(root.right)
    return result

迭代实现（显式栈）

def preorder_iterative(root: Optional[TreeNode]) -> List[int]:
    """
    迭代前序遍历（使用栈模拟递归）
    
    关键技巧:
        - 先压右子节点，再压左子节点（栈LIFO，左先出）
        - 根节点最先访问，符合“根左右”顺序
    
    步骤:
        1. 初始化栈，压入根节点
        2. 当栈非空：
            a. 弹出栈顶，记录值
            b. 若有右子，压入右子
            c. 若有左子，压入左子
    """
    if not root:
        return []
    
    stack, result = [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

Morris 前序遍历（空间O(1)，进阶）

def preorder_morris(root: Optional[TreeNode]) -> List[int]:
    """
    Morris遍历：利用叶节点右指针建立临时链接，遍历后恢复
    
    核心思想:
        对每个节点：
          - 若无左子，访问并移至右子
          - 若有左子：
              a. 找左子树最右节点（前驱）
              b. 若前驱右指针为空，建立到当前节点的链接，访问当前，移至左子
              c. 若已建立链接，断开链接，移至右子
    
    空间复杂度: O(1)
    时间复杂度: O(n) — 每条边最多遍历两次
    """
    result = []
    current = root
    
    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            # 找前驱节点（左子树最右）
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            
            if not predecessor.right:
                # 建立临时链接
                predecessor.right = current
                result.append(current.val)  # 访问根（前序）
                current = current.left
            else:
                # 恢复树结构
                predecessor.right = None
                current = current.right
    return result

---

▶ 2. 中序遍历（In-order: Left → Root → Right）

递归实现

def inorder_recursive(root: Optional[TreeNode]) -> List[int]:
    """
    递归中序遍历
    
    执行顺序:
        1. 递归遍历左子树
        2. 访问当前节点
        3. 递归遍历右子树
    
    BST应用: 输出升序序列
    """
    if not root:
        return []
    result = []
    result.extend(inorder_recursive(root.left))
    result.append(root.val)
    result.extend(inorder_recursive(root.right))
    return result

迭代实现（经典栈方法）

def inorder_iterative(root: Optional[TreeNode]) -> List[int]:
    """
    迭代中序遍历
    
    关键技巧:
        - 一路向左到底，沿途节点入栈
        - 弹出栈顶访问，转向其右子树
        - 重复直到栈空且无当前节点
    
    为什么有效？
        左子树全部入栈后，栈顶即为“最左节点”，访问后其右子树成为新子问题
    """
    stack, result = [], []
    current = root
    
    while stack or current:
        # 1. 一路向左，全部入栈
        while current:
            stack.append(current)
            current = current.left
        
        # 2. 弹出栈顶（此时无左子），访问
        current = stack.pop()
        result.append(current.val)
        
        # 3. 转向右子树
        current = current.right
    
    return result

---

▶ 3. 后序遍历（Post-order: Left → Right → Root）

递归实现

def postorder_recursive(root: Optional[TreeNode]) -> List[int]:
    """
    递归后序遍历
    
    执行顺序:
        1. 递归遍历左子树
        2. 递归遍历右子树
        3. 访问当前节点
    
    应用场景:
        - 删除树（先删子节点）
        - 计算目录大小（先算子目录）
        - 表达式树求值
    """
    if not root:
        return []
    result = []
    result.extend(postorder_recursive(root.left))
    result.extend(postorder_recursive(root.right))
    result.append(root.val)
    return result

迭代实现（双栈法）

def postorder_iterative_dualstack(root: Optional[TreeNode]) -> List[int]:
    """
    双栈迭代后序遍历
    
    思路:
        栈1：模拟前序遍历但顺序为 根→右→左
        栈2：接收栈1弹出的节点
        最终从栈2弹出即得 左→右→根
    
    步骤:
        1. 根入栈1
        2. 当栈1非空：
            a. 弹出节点，压入栈2
            b. 压入左子（若有）
            c. 压入右子（若有）
        3. 依次弹出栈2得到后序序列
    """
    if not root:
        return []
    
    stack1, stack2, result = [root], [], []
    
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    
    while stack2:
        result.append(stack2.pop().val)
    
    return result

单栈+状态标记法

def postorder_iterative_onestack(root: Optional[TreeNode]) -> List[int]:
    """
    单栈迭代后序遍历（带访问状态标记）
    
    状态设计:
        (node, visited) — visited=False表示首次访问，需继续探左/右；True表示子树已遍历完，可访问输出
    
    步骤:
        1. 压入 (root, False)
        2. 当栈非空：
            a. 查看栈顶
            b. 若未访问：
                - 标记为已访问（不弹出）
                - 依次压入右子(False)、左子(False)（注意顺序！）
            c. 若已访问：
                - 弹出并记录值
    """
    if not root:
        return []
    
    stack, result = [(root, False)], []
    
    while stack:
        node, visited = stack.pop()
        if visited:
            result.append(node.val)
        else:
            # 重新压入，标记已访问
            stack.append((node, True))
            # 先压左？不！后序是左→右→根，所以要先压右再压左，让左先处理
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    
    return result

---

（二）广度优先遍历 —— 层序遍历（BFS）

标准层序（按层分组）

from collections import deque

def level_order_grouped(root: Optional[TreeNode]) -> List[List[int]]:
    """
    分层输出层序遍历结果
    
    核心技巧:
        - 使用队列
        - 每层开始前记录当前层节点数（queue长度）
        - 一次性处理完该层所有节点，再进入下一层
    
    时间复杂度: O(n)
    空间复杂度: O(w) — w为最大层宽（最宽层节点数）
    """
    if not root:
        return []
    
    queue = deque([root])
    result = []
    
    while queue:
        level_size = len(queue)  # 当前层节点数
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result

扁平化层序（一维列表）

def level_order_flat(root: Optional[TreeNode]) -> List[int]:
    """不按层分组，直接返回一维列表"""
    if not root:
        return []
    
    queue, result = 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

逆层序遍历（从最底层向上）

def level_order_reverse(root: Optional[TreeNode]) -> List[List[int]]:
    """自底向上分层输出"""
    if not root:
        return []
    
    queue = deque([root])
    result = []
    
    while queue:
        level_size = len(queue)
        current_level = []
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(current_level)
    
    return result[::-1]  # 反转结果列表

---

四、复杂度分析与边界处理大全

时间复杂度统一结论

所有遍历算法时间复杂度均为 O(n) —— 每个节点被访问恰好一次。

空间复杂度对比

遍历方式	递归空间复杂度	迭代空间复杂度	备注
前序/中序/后序	O(h)	O(h) — 栈深度	h为树高，最坏O(n)
层序遍历	不适用	O(w) — 最大层宽	完全二叉树时w≈n/2
Morris遍历	O(1)	O(1)	修改树结构，需恢复

最坏情况：退化树（链表状）→ h = n → DFS空间复杂度O(n)

---

边界条件处理清单

所有函数必须处理：

if root is None:
    return []   # 或 return 0 / None，根据函数语义

节点访问前检查是否为None（尤其在迭代中）

栈/队列操作前检查是否为空

递归基线条件明确（叶节点或空节点）

---

五、工程最佳实践与面试高频考点

工程规范

1. 类型标注必写：

   from typing import Optional, List
   def func(root: Optional[TreeNode]) -> List[int]: ...
   

2. 异常安全：

   • 不假设输入有效性，主动检查 None
   • 不修改原树结构（除非明确要求，如Morris遍历需恢复）

3. 命名清晰：

   • preorder_recursive, inorder_iterative 等明确标识实现方式
   • 避免 traversal1, func2 等无意义命名

4. 性能注释：

   # 时间: O(n), 空间: O(h) — h为树高
   

---

面试高频变形题

1. Zigzag层序遍历（LeetCode 103）

   • 奇数层从左到右，偶数层从右到左
   • 解法：层序遍历 + 按层号反转列表

2. 右视图/左视图（LeetCode 199）

   • 每层最后一个/第一个节点
   • 解法：层序遍历取每层末元素

3. 验证是否为BST（LeetCode 98）

   • 中序遍历应为严格升序

4. 最近公共祖先LCA（LeetCode 236）

   • 后序遍历思想：自底向上找共同祖先

5. 路径总和系列（LeetCode 112, 113, 437）

   • 前序遍历 + 回溯

---

六、总结对比表

特性	前序遍历	中序遍历	后序遍历	层序遍历
访问顺序	根→左→右	左→根→右	左→右→根	层级从左到右
递归实现难度	★☆☆☆☆	★★☆☆☆	★★★☆☆	不适用
迭代实现难度	★★☆☆☆	★★★☆☆	★★★★☆	★★☆☆☆
BST应用	复制树	输出排序序列	删除节点	层级分析
表达式树	前缀表达式	中缀表达式	后缀表达式	-
空间复杂度	O(h)	O(h)	O(h)	O(w)
是否可Morris	✅	✅	✅（较复杂）	❌
面试出现频率	★★★★☆	★★★★★	★★★★☆	★★★★☆

---

七、学习路线建议

如果觉得本文对您有所帮助，请点个赞和关注吧，谢谢！！！你的支持就是我持续更新的最大动力