236. 二叉树的最近公共祖先

解法一：Path，寻找路径，看路径最早重合的地方。从根节点往下找，找到需要查找的两个节点的路径，然后判断最早重合点。

时间复杂度：查找第一个节点O(N) + 查找第二个节点O(N) +从根节点开始的最早重合点 ≈ 3O(N) ，忽略常数，最终：O(N)

相对较慢，同时代码复杂，但思维逻辑直接。

特例：从每个节点往上找，就变成了寻找两个链表的重合点，但一般不会有往上的指针，所以是特例。

拓展：因为是树，重合的地方比较好判断，如果不是树呢？这里就有了一个新问题，链表重合：剑指 Offer 52. 两个链表的第一个公共节点

解法二：递归（Recursion），使用一个辅助函数 findPorQ(root, P, Q)，从以 root 为根的子树上去找 P 和 Q，返回任意一个均可。

伪代码：

fun findPorQ(root, P, Q){
   if(root == P or root ==Q) return root
   findPorQ(root.left, P, Q)
   findPorQ(root.right, P, Q)
}

原理：层层递归，如果两边都能找到 P 或者 Q，说明当前节点就是公共节点。

如果一侧找不到为空，则可以放弃为空的那一侧，继续递归另一侧。

Java 代码很好理解（注意嵌套的三目运算符）：

变种题：235. 二叉搜索树的最近公共祖先

解法：根据二叉搜索树的规律，判断 P 和 Q 与 root 节点的相对关系即可。P，Q 都小于 root 则在左子树中，都大于则在右子树中，刚刚一大一小则当前就是。

Python 版本：递归

非递归：