这里的二叉树不一定是二叉搜索树。
可以将其结构表示为 -
struct node {
int data;
struct node *left;
struct node *right;
};
我和我的朋友想到的最优解如下:考虑这个二叉树:
其中序遍历结果为:8,4,9,2,5,1,6,3,7
后序遍历结果为:8,9,4,5,2,6,7,3,1
例如,如果我们要找到节点8和5的公共祖先,则需要在中序遍历时列出所有位于8和5之间的节点,而在此示例中,它们是[4,9,2]。然后我们检查此列表中最后出现在后序遍历中的节点,即2。因此,8和5的公共祖先是2。
我认为该算法的复杂度为O(n)(中序/后序遍历的O(n),其余步骤再次为O(n),因为它们仅是数组中的简单迭代)。但很有可能我错了。:-)
但这只是一个非常粗略的方法,我不确定是否有一些情况会失效。还有其他(可能更优)的解决方案吗?