二叉树（题单顺序）

为了让测试用例可运行，本页代码里会自带 TreeNode、buildTree 等小工具（不影响 LeetCode 提交）。

• 中序遍历顺序：左 → 根 → 右。
• 递归很好写，但迭代要自己维护“回来的路”：这条“回来的路”就是栈。
• 推理流程：
  • 只要能往左走，就一直把节点压栈（表示“我回来还要处理它和它的右子树”）。
  • 走到最左空了，就弹栈：此时左边都处理完了，轮到“根”。
  • 处理完根后，再去它的右子树，重复上述过程。
• 不变量：栈里存的是“左子树已经走到底但根还没输出”的节点路径。
• 为什么一定按这个顺序压栈/弹栈？
  • 你可以把它当成“手动展开递归”：递归在进入左子树前会把当前节点压到调用栈里，等左子树处理完再回来处理根和右子树；迭代栈就是在模拟同一件事。
• 复杂度：每个节点入栈/出栈各一次，时间 (O(n))；栈深度最多树高 (O(h))。

• 深度的定义：从根到最远叶子的节点数。
• 关键推理：站在一个节点上，它的最大深度就是：
  • 如果是空节点：深度 0
  • 否则：1 + max(左子树最大深度, 右子树最大深度)
• 这就是典型的树形递归：把“大问题”拆成两个子问题。
• 小例子：根的左子树深度 2、右子树深度 3，那么整棵树深度就是 1 + max(2,3) = 4。
• 复杂度：每个节点访问一次，时间 (O(n))，递归栈深度 (O(h))。

• 翻转的定义：每个节点都交换它的左子树和右子树。
• 为什么递归最自然：树的操作通常都是“当前节点做一次操作 + 递归处理子树”。
• 推理顺序：
  • 先把左右子树分别翻转（或者先交换再翻转也行）
  • 再把它们互换挂回去
• 每个节点恰好访问一次，时间 (O(n))。
• 为什么不会丢节点？：我们只是交换指针指向（left/right），并没有创建/删除节点；递归会把原本的子树继续翻转完再挂回去。
• 复杂度：时间 (O(n))，递归栈 (O(h))。

• 对称的本质不是“值相同”这么简单，而是结构和对应位置都要像镜子一样。
• 关键推理：把问题改成“判断两棵树是否互为镜像”：
  • 两棵树镜像 ⇔ 根值相同，且：
    • 左树的左子树 ⇔ 右树的右子树
    • 左树的右子树 ⇔ 右树的左子树
• 用递归对这两对关系做同样检查即可。
• 最常见的坑：只比较“每层值是否对称”是不够的，结构（空节点位置）也必须对称。
• 复杂度：每个节点最多比较一次，时间 (O(n))，递归栈 (O(h))。

• 直径是什么：任意两点之间最长路径的边数，不一定经过根。
• 朴素想法：枚举每个节点作为路径拐点再算，容易重复计算。
• 关键推理：直径一定是某个节点的“左最高 + 右最高”：
  • 如果最长路径经过某节点，那么它从左子树某叶子走到右子树某叶子。
  • 这条路径长度就是“左子树高度 + 右子树高度”（按边数）。
• 所以我们写一个求高度的 DFS，同时在每个节点更新一次 best，一趟 DFS 就搞定。
• 为什么能用“高度”来表达？：经过当前节点的最长路径，一定由“左边最深叶子到当前节点” + “右边最深叶子到当前节点”拼起来，而这两段长度就是左右高度。
• 复杂度：后序遍历一次，时间 (O(n))，递归栈 (O(h))。

• 层序遍历就是 BFS：从根开始，一层一层往下扩散。
• 怎么分层？：在进入一层时，队列里正好存着这一层所有节点，所以先记录 size = q.length，然后弹出 size 次就是这一层。
• 不变量：每轮循环开始时，队列只包含“当前层”的节点；处理完 size 个后，队列里变成“下一层”的节点。
• 为什么 size 必须先存下来？：因为你在处理这一层时会不断 push 子节点进队列，如果不锁定 size，就会把下一层也混进当前层。
• 复杂度：每个节点进队/出队一次，时间 (O(n))，空间 (O(w))（w 为最大层宽）。

• 要构造“高度平衡”的 BST，直觉就是：根尽量选中间，这样左右子树大小接近。
• 因为数组有序，取中点做根后：
  • 左边部分都比根小 → 递归建左子树
  • 右边部分都比根大 → 递归建右子树
• 递归到区间为空结束。整体时间 (O(n))，每个元素只用一次。
• 为什么中序遍历能验证结果？：BST 的中序遍历一定是升序；我们用它检查“建出来的树仍能还原原数组”，说明结构符合 BST。
• 复杂度：时间 (O(n))，递归栈深度 (O(\log n))（平衡时）。

• BST 的坑：不是只要 左 < 根 < 右 就行，左子树所有节点都要小于根，右子树所有节点都要大于根。
• 关键推理：每个节点都有“允许的取值范围”：
  • 根：(-∞, +∞)
  • 走到左子树：上界变成当前节点值
  • 走到右子树：下界变成当前节点值
• 只要某个节点越界，就不是 BST。
• 为什么不能只检查父子关系？
  • 因为右子树里的某个节点可能比根还小（典型反例：根 5，右子树里出现 3），它和父节点可能仍满足局部大小关系，但整体违反 BST。
• 复杂度：时间 (O(n))，递归栈 (O(h))。

• BST 的一个黄金性质：中序遍历（左-根-右）输出的序列一定是从小到大。
• 所以“第 k 小”就变成：做一次中序遍历，数到第 k 个节点即可。
• 用迭代栈可以避免递归深度问题；每弹出一次栈，就相当于“访问到一个新的最小值”。
• 为什么是“弹栈时计数”？
  • 因为中序的“访问节点”发生在“左子树处理完之后”，而迭代实现中正对应 cur = stack.pop() 那一刻。
• 复杂度：最坏要走到第 k 个节点，时间 (O(h+k))（最坏 (O(n))），空间 (O(h))。

• 右视图的含义：从右侧看过去，每一层你能看到的“最右边”那个节点。
• 关键推理：按层遍历时，每层的最后一个节点就是最右边：
  • BFS 队列一次弹出一层 size 个节点；
  • 第 size-1 个弹出的就是这一层的最右节点（与入队顺序无关，只要同层都处理到即可）。
• 另一种等价做法是 DFS 先走右子树并记录“第一次到达某层”的节点。
• 为什么“最后一个”一定是可见的？：同层节点从左到右排列，右侧视角只能看到最右端的那个（其它都被挡住）。
• 复杂度：时间 (O(n))，空间 (O(w))。

• 目标结构：按前序遍历顺序，把树“拉直”成只用 right 指针的链表，且 left 全部置空。
• 关键推理：如果我们从后往前把节点串起来会更容易：
  • 最终链表的“下一个”是谁？就是前序遍历里当前节点的下一个节点。
  • 反过来想：如果我们按“前序的逆序”遍历（右→左→根），就能在回溯时用一个 prev 指针把链表串起来：
    • 当前节点的 right 指向 prev
    • 更新 prev = 当前节点
• 为什么是右→左→根？：前序是 根→左→右，逆过来就是 右→左→根。
• 为什么要把 left 置空？：题目要求展开后是“只用 right 指针”的链表，如果 left 不置空就不符合输出结构。
• 复杂度：每个节点访问一次，时间 (O(n))，递归栈 (O(h))。

• 前序的第一个一定是根：因为前序是 根→左→右。
• 中序里根的位置把左右子树切开：中序是 左→根→右，所以根左边都是左子树，根右边都是右子树。
• 递归构造的推理：
  1. 取当前前序指针 prePos 指向的值作为根
  2. 在中序中找到根的位置 mid
  3. 递归构造左子树（中序区间 [inL, mid-1]）
  4. 递归构造右子树（中序区间 [mid+1, inR]）
• 为什么要 Map 加速？：不然每次找根在中序的位置都要线性搜索，会退化成 (O(n^2))；用 Map 后整体 (O(n))。
• 为什么递归区间长度正确？
  • 中序中 mid 左边的长度就是左子树节点数；而前序会按“根→左→右”消费节点，所以只要用 prePos 作为全局游标，递归自然会按正确数量把节点分配给左/右子树。
• 复杂度：每个节点只创建一次，查位置 (O(1))，总时间 (O(n))，递归栈 (O(h))。

• 路径定义：从某个节点往下走到某个节点（必须向下），不要求从根开始，也不要求到叶子结束。
• 朴素做法：以每个节点为起点做一次 DFS 累加，会重复很多，最坏 (O(n^2))。
• 关键推理：把树上的“路径和”也写成前缀和差值：
  • 在一条从根到当前节点的路径上，设 prefix 是到当前节点的累计和。
  • 如果某段向下路径和为 target，就意味着：存在一个祖先前缀 oldPrefix，使得 prefix - oldPrefix = target，也就是 oldPrefix = prefix - target。
  • 所以到达一个节点时，只要知道“当前路径上有多少个前缀和等于 prefix-target”，就能一次性统计出所有以当前节点为结尾的合法路径数。
• 为什么要回溯减频次？
  • freq 只应该统计“当前这条根到当前节点路径”上的前缀和。
  • DFS 走完一个子树回到父节点时，要把子树路径上的前缀和移除，否则会把另一条分支当成同一路径，统计出错误答案。
• 为什么这能覆盖“不从根开始”的路径？
  • 因为我们统计的是“当前 prefix 与历史 prefix 的差值”，历史 prefix 可以来自任意祖先节点，所以对应的路径起点也可以是任意节点。
• 复杂度：每个节点进出一次，时间 (O(n))，空间 (O(h))（Map 在一条根到叶路径上的前缀和数量）。

• 最近公共祖先：离 p、q 最近的那个“同时是它们祖先”的节点。
• 关键推理：后序遍历最合适（先处理子树，再决定当前节点）：
  • 让 DFS 返回一个布尔值：当前子树里是否包含 p 或 q。
  • 当前节点成为 LCA 的三种情况：
    1. 左子树找到一个，右子树找到一个（分居两侧）
    2. 当前节点本身是 p/q，且左/右子树里找到另一个
• 一旦满足，就把 ans 记录下来。
• 为什么要用后序？
  • 因为“当前节点是否是 LCA”取决于左右子树各自是否包含目标节点，必须先知道子树结果再做判断（先子后父）。
• 复杂度：每个节点访问一次，时间 (O(n))，递归栈 (O(h))。

• 路径定义：可以从任意节点到任意节点，但必须沿父子连接走；路径可以在某个节点“拐弯”一次（左右各走一段），但不能分叉成三条。
• 两个概念要分清：
  1. 全局最优路径：可能在任意位置拐弯，所以需要一个全局 best。
  2. 向上贡献值：返回给父节点时，路径不能左右都拿（否则父节点会分叉），所以只能选“左或右里更大的一边”。
• 关键推理（后序）：
  • 先算出左右子树给你的“向上贡献”；如果贡献是负数，等于拖后腿，直接当 0（不选）。
  • 经过当前节点的最佳路径是：node.val + left + right（可以两边都拿，表示在这里拐弯）。
  • 但返回给父节点只能是一条：node.val + max(left, right)。
• 为什么贡献要和 0 比较？
  • 因为路径可以从任意节点开始，如果某一侧贡献为负，选上它只会让总和变小，不如直接在当前节点“重新开始”。
• 复杂度：时间 (O(n))，递归栈 (O(h))。