LCA 分为几种情况
1. Binary Search Tree 的 LCA
2. Binary Tree with parent pointer
3. Binary Tree without parent pointer
4. ordinary Tree without parent pointer
Binary Search Tree
思路
1. 对一个节点 node, 假如 n1,n2 均大/小于 node->val, 那么LCA一定在 node->right 分支上
2. 若一个大于一个小于， 则 LCA 就是 node 本身
3. updown 解法， log(n) 的时间复杂度
Binary Tree with Parent Pointer
思路
1. 先 find 到两个节点， 并记录深度
2. 较深的节点先走深度之差步， 然后两个节点同时向上走，直到相遇
3. 上面几乎就是求解链表的公共节点问题了， 时间复杂度为 o(n), 空间复杂度为常数
Binary Tree without Parent Pointer
Top-Down 解法 worst case， 时间复杂度为 o(n^2)
1. 从 root 开始， 对每一个节点 node 作检测， 若 node 等于两个节点之一， 而返回 node
2. 否则， 检测 node->left 中， 有几个待求 LCA 节点存在（0？1？2？）， 若 0，2 则直接到另一侧子树中去寻找
3. 若为 1， 则说明两个节点在 node 两侧， 返回 node 即可
在树是平衡树时， 每次减半， 时间复杂度计算方法如下：
时间复杂度的计算方法
T(n) = T(n/2) + n/2
a = 1, b = 2, f(n) = n
根据主定理， 时间复杂度为 o(n*logn)
若树是 degenerate 的， 时间复杂度为 o(n^2)
Bottom-up 解法 时间复杂度为 o(n)
上面解法的问题在于重复计算， 而 bottom-up 则致力于解决重复计算
从下到上遍历， 一旦遇到两个节点中的一个， 则将该节点传递到其父亲， 直到两个节点相遇， 返回即可
思路有些抽象， 代码却很简洁
Update 2014年2月24日12:00:56
这实际上就是后序遍历, root 访问之前, 其左右孩子都已被访问过了. 代码的框架和求 depth 一致
Node *LCA(Node *root, Node *p, Node *q) { if (!root) return NULL; if (root == p || root == q) return root; Node *L = LCA(root->left, p, q); Node *R = LCA(root->right, p, q); if (L && R) return root; // if p and q are on both sides return L ? L : R; // either one of p,q is on one side OR p,q is not in L&R subtrees}
一般树的 LCA
使用 dfs 定位两个节点的位置, 并保存路径, 然后求两个链表的公共祖先
主方法
为如下形式的递归式提供了一种“菜谱”式的求解方法，如下所示
其中a≥1和b>1是常数，f(n)是渐近正函数。为了使用主方法，需要牢记三种情况，但随后你就可以很容易地求解很多递归式，通常不需要纸和笔的帮助。
主方法依赖于下面的定理。
定理4.1(主定理) 令a≥1和b>1是常数，f(n)是一个函数，T(n)是定义在非负整数上的递归式：
那么T(n)有如下渐近界：
主定理不能适合于这样的递归式：T(n)=2T(n/2)+nlgn，因为该递归式落入了情况2和情况3之间的间隙。利用主定理计算递归式非常方便，不用再画递归树了。