树与二叉树

1. 一句话总结

树是分层结构，二叉树是每个节点最多两个孩子的树，面试重点是递归、遍历和层序。

2. 通俗解释

树像组织架构，二叉树限制每个人最多两个下属。很多树题都能拆成：当前节点做什么，左子树做什么，右子树做什么。

3. 核心概念

• 根、父节点、子节点、叶子、深度、高度。
• 二叉树：每个节点最多有左右两个孩子。
• 前序：根 → 左 → 右。
• 中序：左 → 根 → 右。
• 后序：左 → 右 → 根。
• 层序：按层遍历，用队列。

4. 底层原理

• 树天然适合递归，因为子树和原问题结构相同。
• 前序适合复制结构，中序适合 BST 有序输出，后序适合计算子树信息。
• 层序遍历用队列保存下一层节点。
• 遍历时间通常 O(n)，递归空间取决于树高。
• 平衡树高度 O(log n)，链状树高度 O(n)。

5. 面试标准回答

树和二叉树的核心是层级关系和递归结构。二叉树每个节点最多两个孩子，因此很多问题可以写成处理当前节点、递归处理左子树、递归处理右子树。前序遍历先访问根节点，适合输出结构；中序遍历对 BST 会得到有序序列；后序遍历先处理子树，适合计算高度、删除节点等问题；层序遍历用队列按层访问。大多数遍历访问每个节点一次，时间 O(n)，空间看树高。

6. 高频追问

追问 1：树与二叉树面试第一句话怎么答？

先给结论：根、父节点、子节点、叶子、深度、高度。 再补充它解决的问题和使用场景，避免一上来背长定义。

追问 2：它为什么需要底层机制支撑？

树天然适合递归，因为子树和原问题结构相同。 面试官追问时要把“现象”落到“机制”和“代价”。

追问 3：常见误区是什么？

不要把平均情况说成绝对结论，也不要忽略边界条件、退化情况和工程成本。

追问 4：如果继续追问怎么展开？

可以沿着“定义 → 原理 → 对比 → 场景 → 缺点 → 优化”展开，重点说清：前序适合复制结构，中序适合 BST 有序输出，后序适合计算子树信息。

追问 5：实际开发中怎么体现？

文件目录、DOM 树、组织架构都可用树表达。 这类联系能把基础知识从“背概念”变成“解释工程选择”。

追问 6：回答时怎么收尾？

最后用一句话总结适用条件和代价，说明什么时候该用、什么时候不该用。

7. 易混淆点

8. 实际开发联系

• 文件目录、DOM 树、组织架构都可用树表达。
• MySQL B+ 树索引是多叉树思想应用。
• JSON/XML 解析经常涉及树遍历。

9. 背诵速记

树题抓递归：空节点返回什么，当前节点做什么，左右子树返回什么。前序根左右，中序左根右，后序左右根，层序用队列。时间通常 O(n)，空间看树高。