在二叉树中找到最不常见的父树？

Question

这个问题可能被很多人问过，但是，它有点不同。我们有一个二叉树。给你两个节点p&q。我们得找到最不常见的父母。但是您没有指向根的根节点指针。为您提供了两个内置函数，它们是：

如果节点c实际上是root，那么parentNode函数将返回null值。使用这些函数，我们必须找到树中最不常见的父树。

Answer 1

步骤1：使用parentnode函数查找节点p与根的距离d1。类似地，查找节点q与根的距离d2。（例如，d2出来时大于d1)步骤2：将更远的节点（其D值更大）指针d2-d1步骤移向根。步骤3：同时将指针P和Q移向根，直到它们指向同一个节点并返回该节点。

基本上，这就像找到两个链接列表的合并点一样。
检查下面的链接：检查两个链表是否合并。如果有，在哪里？时间复杂性:O(N)
您的代码看起来大致如下:

node* LCP(node* p, node *q){
    int d1=0, d2=0;
    for(node* t= p; t; t = parentNode(p), ++d1);
    for(node* t= q; t; t = parentNode(q), ++d2);
    if(d1>d2){
        swap(d1, d2);
        swap(p, q);
    }
    for(int i=0; i<(d2-d1); ++i)
        q = parentNode(q);
    if( same(p, q)){
        return parentNode(p);
    }
    while( !same(p, q)){
        p = parentNode(p);
        q = parentNode(q);
    }
    return p;
}