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

这个问题可能已经被很多人问过了，但是，有点不同。我们有一棵二叉树给你两个节点P&Q，我们必须找到最不常见的父节点。但是没有指向根的根节点指针。我们为您提供了两个内置功能：
1）如果节点相同，则返回true，否则返回false。
2）返回当前节点的父节点。
如果节点c实际上是根节点，那么parentNode函数将返回一个BOOL same(node *p, node *q);值。
使用这些函数，我们必须找到树的最不常见的父级。

最佳答案

假设C++：

node* leastCommonParent(node *p, node *q)
{
    node *pParent = parentNode(p);
    while(pParent != 0)
    {
        node *qParent = parentNode(q);
        while(qParent != 0)
        {
            if (0 == same(pParent, qParent))
                return pParent;
            qParent = parentNode(qParent);
        }
        pParent = parentNode(pParent);
    }
    return 0;
}

更新：下面是一个没有使用递归显式声明变量的版本我相信它可以改进，而且可能永远不会在当前形式的生产代码中使用它。

node* qParent(node *p, node *q)
{
    if (p == 0 || q == 0)
        return 0;
    if (same(p, q) == 0)
        return p;
    return qParent(p, q->parent);
}

node* pParent(node *p, node *q)
{
    return qParent(p, q) ? qParent(p, q) : pParent(p->parent, q);
}

node * result = pParent(p, q);

关于algorithm - 在二叉树中找到最不常见的父级？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13283291/