algorithm - 如何找到任何二叉树中两个节点的最低公共(public)祖先？

Question

这里的二叉树不一定是二叉搜索树。
该结构可以视为 -

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

我能和 friend 一起解决的最大解决方案是这样的——
考虑 this binary tree :

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

但这是一种非常粗略的方法，我不确定它是否会在某些情况下失效。这个问题是否有其他(可能更优)的解决方案？

Answer 1

从 root 节点开始向下移动，如果您找到任何以 p 或 q 作为其直接子节点的节点，那么它就是生命周期评估。 (编辑 - 这应该是如果 p 或 q 是节点的值，返回它。否则当 p 或 之一时它将失败>q 是另一个的直接子代。)

否则，如果您发现一个节点在其右(或左)子树中具有 p 且在其左(或右)子树中具有 q 那么它就是 LCA。

固定代码如下:

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is the root then root is LCA.
        if(root==p || root==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

当任何一个是另一个的直接子级时，下面的代码将失败。

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is direct child of root then root is LCA.
        if(root->left==p || root->left==q || 
           root->right ==p || root->right ==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

Code In Action