1. 表达式树 Expression Tree#

树的叶子节点通常是操作数（例如数字或变量）, 而非叶子节点是运算符（例如 +、-、*、/）, 通过遍历表达式树（例如前序、中序或后序遍历），可以重新生成表达式或计算其结果, 表达式 (3 + 5) * 2 可以表示为：

    *
   / \
  +   2
 / \
3   5
  • 计算器程序：实现复杂数学计算时，表达式树可以帮助按正确的顺序执行运算（尊重运算优先级和括号）
  • 数据库查询优化：在 SQL 查询引擎中，表达式树可以表示查询条件，帮助优化执行计划

2. 决策树 Decision Tree#

决策树是一种树形结构, 用于表示决策过程或分类/回归问题, 树的每个节点代表一个决策点（基于某个条件）, 分支代表可能的决策路径, 叶子节点通常表示最终的决策结果或类别:

       [天气]
      /      \
  [晴天]    [下雨]
  /           \
[外出]      [待在家]
  • 机器学习：决策树是经典的监督学习算法，用于分类和回归任务。例如，判断用户是否会购买某产品（基于年龄、收入等特征）
  • 游戏开发：在 AI 行为设计中，决策树用于控制 NPC（非玩家角色）的行为，例如决定是否攻击或逃跑
  • 医疗诊断：基于症状、体征等条件，决策树可以帮助医生判断疾病类型

3. 二叉搜索树 Binary Search Tree, BST#

  • 利用 BST 的性质：若目标值小于当前节点，向左子树查找；若大于，向右子树查找

  • 时间复杂度：平均 O(log n)，最坏 O(n)（退化为链表时）

Node find(Node root, int value) {
    if (root == null || root.value == value) return root;
    if (value < root.value) return find(root.left, value);
    return find(root.right, value);
}

延伸：提到退化问题，并引出平衡树（如 AVL 或红黑树）

如何判断一棵树是否是二叉搜索树？

中序遍历检查是否升序

bool isBST(Node root, int min, int max) {
    if (root == null) return true;
    if (root.value <= min || root.value >= max) return false;
    return isBST(root.left, min, root.value) && isBST(root.right, root.value, max);
}

4. 遍历二叉树 - DFS#

Recursion 三步

  • 确定终止条件
  • 确定单层逻辑
  • 确定返回值和参数

其实首先要确定的应该是遍历顺序, 因为遍历顺序决定了递归的顺序, 递归的顺序决定了返回值和参数, 且听我慢慢说来

class Solution104:
    def __init__(self):
        self.current_depth = 0
        self.max_depth = -1

    def maxDepth(self, root):
        def preorder(node):
            if not node:
                return
            
            # 前序遍历 中左右
            self.current_depth += 1
            if self.max_depth < self.current_depth:
                self.max_depth = self.current_depth

            if node.left:
                preorder(node.left)
                self.current_depth -= 1
            if node.right:
                preorder(node.right)
                self.current_depth -= 1

        preorder(root)
        return self.current_depth

前序遍历使用场景: 函数处理当前节点再进行递归处理其他子节点 中左右 递归函数的单层逻辑都是处理当前节点, 一般我们通过一个全局变量 (比如上面的 max_depth) 来作为参数来传递 (积累) 每次 recursion 的影响

而后序遍历适合通过返回值的方式来传递信息, 因为当前节点最后处理, 通过下面的例子可以看出:

def maxDepth(root):
    if not root:
        return 0
    # 后序遍历 左右中
    left = self.maxDepth(root.left)
    right = self.maxDepth(root.right)
    return max(left, right) + 1

DFS 是 “Depth-First Search” 的缩写，中文翻译为“深度优先搜索”

  • 深度优先：指的是在搜索过程中，优先沿着一条路径尽可能深入，直到无法继续深入为止（到达尽头或满足某个条件），然后回溯到上一个节点，再探索其他路径

  • 搜索过程：从起点开始，选择一个方向深入探索，访问完一个节点后，继续访问它的子节点，而不是立即访问同一层的其他节点

在二叉树遍历的上下文中，DFS 通常表现为递归调用，因为递归天然具有“深入到底再回溯”的特性:

  • 前序遍历：先访问根节点，然后深度优先遍历左子树，再遍历右子树

  • 中序遍历：先深度优先遍历左子树，然后访问根节点，再遍历右子树

  • 后序遍历：先深度优先遍历左子树，再遍历右子树，最后访问根节点

DFS 的特点

  • 可以用递归
  • 也可以用栈
  • 空间复杂度：O(h)，h 是树的高度或图的最大深度，因为需要存储递归调用栈或显式栈
  • 时间复杂度：O(n)，n 是节点数，因为每个节点都会被访问一次

BFS（广度优先搜索，Breadth-First Search）：一层一层地探索，先访问所有同一层的节点

5. 平衡二叉树 Balanced Binary Tree，如 AVL 树、红黑树#

如何平衡一棵二叉搜索树？问题变种：AVL 树和红黑树的区别？

  • AVL 树：通过旋转（左旋、右旋）保持高度差 ≤ 1，插入/删除后严格平衡，适合读多写少的场景
  • 红黑树：通过颜色规则和旋转维持近似平衡，插入/删除效率更高，适合写多读少的场景（如标准库实现）
  • 区别：AVL 树更严格，查找更快（O(log n) 更稳定）；红黑树更宽松，插入/删除更快
  • 延伸：可以提到自底向上或自顶向下的平衡过程