树

树是递归变得自然的数据结构。大多数树问题遵循深度优先搜索（DFS），先深入再回溯，或广度优先搜索（BFS），逐层处理。DFS 通常是递归的，适合基于路径的问题，而 BFS 使用队列，适合基于层级或最短路径的问题。一个关键习惯是区分函数返回的内容和它作为副作用记录的内容，因为许多问题需要在局部递归决策的同时跟踪全局答案。线段树和 Fenwick 树将这些概念扩展到可变数组的范围查询，尽管它们在竞赛编程中比标准面试中出现得更频繁。