相关疑难解决方法(0)

这里的二叉树可能不一定是二进制搜索树.
结构可以视为 -

struct node {
    int data;
    struct node *left;
    struct node *right;
};

我可以和朋友一起解决的最大解决方案就是这种 -
考虑这个二叉树:

二叉树http://lcm.csa.iisc.ernet.in/dsa/img151.gif

顺序遍历产量 - 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),因为它们只不过是数组中的简单迭代).但这很有可能是错误的.:-)

但这是一个非常粗略的方法,我不确定它是否会因某些情况而崩溃.这个问题还有其他(可能是更优的)解决方案吗？