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

[题目]

求二叉树的任意两个节点的最近公共祖先。

此题有多个扩展问题：

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

Example

1                 /     \               2        3            /     \         \          4      5          6

对于左侧二叉树， 节点 4 ， 5的最近公共祖先是2，节点5，6的最近公共祖先是1

[澄清]

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

[思路]

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

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

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

对于第二个问题，最简单的方法肯定是将第一个方法执行多遍，但必然存在优化的空间。我们可以从如下两个角度来考虑优化：

首先，可以考虑预处理和缓存。也就是说，当某组查询发生过以后将其结果缓存起来，如果后来的查询还有查到此数据的，可以将其从缓存里直接返回。我们可以预处理一些数据事先缓存起来，以供查询时调用。这种方法可以是每次查询时每一组数据的平均时间复杂度可以降低到O(1) * k/n^2 + O(n) * (n^2 - k)/n^2 = O(n - ((n-1)k)/n^2)  . 其中k表示的缓存多少组数据。空间复杂度也就上升到了O(k). 这种思想是典型的空间换时间的方法，在是集中比较常用。

还有一种优化的方法是设法重新排序他给出的查询序列，使得可以通过一次遍历来取得所有的查询结果。通过观察，我们可以将查询序列（p11, p12) ,（p21, p22), … (pn1, pn2) 按照第一个查询节点p11, p21, …, pn1 的在树中后序访问序列递增排序。我们在进行后续遍历树的时候可以在O（n)时间中找到每个被查询第一个节点的后续位置。然后我们在把查询序列按照第二个查询节点p12, p22, …, pn2在树种的后续访问节点的递增排序。我们在进行后续遍历时可以在 O(n)时间中查找到每个查询第二个节点的后续位置。我们可以再在O（n)的遍历中找到每组查询第一个节点和第二个节点后续位置之间序列节点的depth最小值。这个最小值就是此组查询结果。虽然过程有些复杂，但依然可以在O(n)复杂度中查找到所有查询的结果。使用此种方法时，需要O(m)的缓存空间来存放临时数据。其中m是给出的查询序列的大小。

[代码]

public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

       if (root == null) return null;

       

       if (root == p || root == q) return root;

       

       // Post order traveral

       TreeNode l = lowestCommonAncestor(root.left, p, q);

       TreeNode r = lowestCommonAncestor(root.right, p, q);

       

       if (l != null && r != null) {

           return root;

       } else {

           return l != null ? l : r;

       }

   }

[面试官角度]

此题主要考察被面试者对基本数据结构（比如树）的清晰程度，能否灵活应用学到的算法基础。同时，也会附带考察到面试者工程经验。此题除了第二问的第二种解法外，其他难度都不大，但都很考察面试者的基本功，是一道常见的面试题。在实际面试中，第二问的第二种解法并不一定需要给出正确的答案，如果能有一些思路，那已经是很大的加分了。

[Reference]

http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-ii.html