求二叉树的任意两个节点的最近公共祖先。 |
---|
此题有多个扩展问题:
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)。
.....