树题先定义递归函数返回什么，再决定当前节点在子树结果之前还是之后处理。

🧭 什么时候考虑这个专题

需要分层使用 BFS；需要子树汇总信息使用后序 DFS；BST 查询与验证利用全局有序边界。

开始编码前先明确输入、输出、数据规模和允许修改的数据，再用一句话写出循环、窗口、堆或递归函数保持的不变量。

核心结构与复杂度

知识点核心规则常见复杂度
前中后序语义根节点在递归处理前、中、后的相对位置决定遍历顺序访问整棵树 O(n)
递归深度递归 DFS 的调用栈与树高成正比空间 O(height)
BFS 峰值空间层序遍历队列峰值与树的最大宽度相关空间 O(width)
BST 全局边界验证 BST 必须把祖先给出的上下界传递到整棵子树时间 O(n)
自底向上平衡判断后序一次返回子树高度并用特殊值传播不平衡时间 O(n)

复杂度必须对应真实代码路径。哈希结构要区分平均与最坏情况，递归要计算调用栈，返回结果是否计入空间也应按题目口径说明。

适用边界

  • 前中后序语义： 具体选择取决于任务需要根信息还是子树结果
  • 递归深度： 退化链形树的栈空间可达到 O(n)
  • BFS 峰值空间： 平衡树最后一层可能包含 O(n) 节点
  • BST 全局边界： 只比较父节点与直接孩子无法发现跨层违规
  • 自底向上平衡判断： 每个节点只能计算一次高度才能保持 O(n)

C# 实现检查

  1. 方法签名与题目契约一致，不依赖控制台输入输出。
  2. 数值计算检查 int 溢出，必要时先提升为 long。
  3. 集合选择说明平均复杂度、顺序语义和重复值处理。
  4. 字符串题明确使用 char、Rune、序号比较还是文化比较。
  5. 递归题说明终止条件、最大深度和退化输入。

⚠️ 常见误区

  • 前中后序语义： 不要把“三种遍历只是在输出位置上随意调整”当成规则。
  • 递归深度： 不要把“树遍历递归栈始终是 O(log n)”当成规则。
  • BFS 峰值空间： 不要把“BFS 的额外空间始终是 O(1)”当成规则。
  • BST 全局边界： 不要把“每个节点大于左孩子且小于右孩子就足够”当成规则。
  • 自底向上平衡判断： 不要把“对每个节点重复求左右高度仍是 O(n)”当成规则。

练习顺序

先完成本组 5 道选择题，口述每个选项的边界；再独立实现编程题，最后对照参考答案检查不变量、复杂度和面试追问。