如题。
分析:
假设这棵树的每个结点都有n的指针指向n棵子树,可能有的子树为空。
已知的两个结点的关系有两种情况:
一个结点是另一个结点的祖先,这种情况第一个结点是两个结点的共同祖先;
第三个结点是两个结点的共同祖先。
算法:
递归遍历每个结点,
如果当前结点是空结点,返回NULL,
如果当前结点等于两个结点中的一个,返回当前结点指针
递归遍历当前结点的所有子树,返回n个结点指针,
如果只有一个指针非NULL,说明两个结点都在那棵子树中,返回那棵子树的指针,
如果有两个指针非NULL,说明当前结点是这两个结点的共同祖先,返回当前结点指针。