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

Question

这个问题可能已经被很多人提出过,但是,它有点不同.我们有一棵二叉树.而且你有两个节点p&q.我们必须找到最不常见的父母.但是你没有指向根的根节点指针.您将获得两个内置功能:

1)BOOL same(node *p, node *q);- >如果节点相同则返回true,否则返回false.

2)node* parentNode(node *c);- >返回一个节点,该节点是当前节点的父节点.

如果节点c实际上是root,那么parentNode函数将返回一个NULL值.使用我们必须的函数来查找树的最不常见的父代.

Answer 1

步骤1:使用parentNode函数查找d1节点p与根的距离.类似地找到d2节点q与根的距离.(比如说,d2大于d1)

步骤2:移动更远的节点(其d值越大)指针d2-d1指向根.

步骤3:同时移动指针p并q朝向root,直到它们指向同一节点并返回该节点.

基本上它就像找到两个链表的合并点.
检查以下链接: 检查两个链接列表是否合并.如果是的话,在哪里？

时间复杂度: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;
}