How to find the lowest common ancestor in a tree 最近公共祖先

[题目]

此题有多个扩展问题：

1. 如果只查询一次，二叉树给出向上（parent）链接和不给向上链接时分别有什么解法，最佳空间时间复杂度是多少？
2. 如果一次性给出多组查询，解法能有什么改进，空间时间复杂度又是什么？

Example

[澄清]

在面试中，面试者一般不直接告诉你树是否有向上链接，能否自定义树的node，而这类信息对此题的解法复杂度又有相当重要的影响，面试时应该主动向面试者提出。

[思路]

对于第一问：如果有向上链接，我们只要先求出给定的两点p1, p2分别到root的距离，以及他们的插值（假设为d）。然后将距离较长的点（假设为p1)沿树向上行走直d步。最后将p1 和 p2 同时向上走直到他们相遇。显然，此次相遇是他们第一次相遇，而相遇时所在的节点也就是最近公共的祖先节点。

如果没有向上链接，我们只能通过遍历树的方法来的到最近公共祖先。可以证明，在一棵树中，最近公共祖先必然是1）p1,p2节点中的一个，或者2）p1,p2分别在其左右子树中。通过后序遍历整棵树，分别判断如上的条件即可得到结果。

如上两种情况，最坏情况下，都需要遍历整棵树，所以时间复杂度都是O(n)；空间复杂度对于树的遍历都是O(1)。

.....