BST 最近公共祖先：走到第一次分流
两边都小走左，两边都大走右。当前值夹在 p、q 之间，或等于其中之一，就是最近的共同祖先。
从根往下：若当前值小于 p、q 两者，LCA 在右子树；大于两者，LCA 在左子树；否则当前节点就是 LCA——p、q 在这里第一次分开，或当前就是其中之一。时间 O(h)，空间 O(1)。
这是 LeetCode 235. Lowest Common Ancestor of a Binary Search Tree。给定 BST 的根和两个不同节点 p、q（二者一定在树里），返回它们的最近公共祖先：同时是两者祖先、且深度最大的那个节点。节点可以是自己的祖先。
主例层序 [6, 2, 8, 0, 4, 7, 9]。p=2、q=8 的 LCA 是根 6，演示第一组帧一步即中。p=0、q=4 都在 6 的左侧，LCA 是 2，演示第二组帧先左再停。
普通二叉树要在左右子树里搜「见到了几个目标」，见 LC236。BST 的左小右大把搜索收成一条向下的路：缺的不是递归三态，而是「当前这一格是否已经把 p、q 分到两侧」。
一次比较，方向唯一
LCA 是 p、q 路径上最后一个共同点。在 BST 里，这个点有数值刻画：它是从根出发、第一个不把 p 和 q 送向同一侧的节点。当前值比两者都小，两者都在右子树，共同点还在下面；比两者都大，都在左子树。否则当前值落在两者之间（含端点），再往下走必然丢掉其中一侧，当前就是最近的共同点。
第一直觉是先找出两条根到目标的路径再对齐，O(h) 空间能做对。缺口是路径本身不必存：每次比较已经告诉你下一步只可能向左或向右或停。p、q 谁大谁小不用预先排序，两个不等式一起写即可。
主例 p=2、q=8。根 6：2<6 且 8>6，6 夹在中间，停。演示 path=[6]，LCA=6。若误以为「根一定是答案」，下一节 0 与 4 会立刻反驳。
BST 的分岔点值介于 p、q 之间（含等于其中之一）= 两人从这里开始不能再走同一条边 = 最近公共祖先。
更深的例子：一路往下
p、q 落在同一侧时，根不是 LCA，继续沿 BST 走。迭代就是一个 while：都小 cur=cur.Left，都大 cur=cur.Right，否则返回 cur。
p=0、q=4。根 6 比两个都大，去左，path 记下 6。来到 2：0<2<4，2 夹在中间，停。演示三帧：先左、再认定 2、答案 2。4 与 7 则相反——4<6<7，根 6 已经分流，不会走进 2。
当前等于 p 或 q 也停。例如 p=2、q=4：根 6 都大，去左；到 2 时 2 等于 p，2 是 4 的祖先，也是自己的祖先，LCA 就是 2。不必先找到较深的那个再往回爬。
Go：迭代
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {cur := rootfor cur != nil {if p.Val < cur.Val && q.Val < cur.Val {cur = cur.Left} else if p.Val > cur.Val && q.Val > cur.Val {cur = cur.Right} else {return cur}}return nil}
1两者都小于 cur，LCA 还在左。主例 0 与 4 对 6 走这里。
2两者都大于 cur，去右。主例没有走到 8 下面，但 7 与 9 会。
3其余情况返回 cur：夹在中间，或 cur 就是 p / q。2 与 8 对 6、0 与 4 对 2，都走这支。
4题目保证 p、q 在树中，正常不会落到 return nil。
总结
都小走左，都大走右，分流即停。主例 2 与 8 停在 6，0 与 4 停在 2。
- BST 有序性让你不必存两条路径。一次比较丢掉一整侧。
- 当前等于 p 或 q 也是答案，节点可以是自己的祖先。
- LC236 没有有序性，必须递归统计左右各见到几个目标。