如何找到任意二叉树中两个节点的最低公共祖先？

Question

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

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)，因为它们只不过是数组中的简单迭代）。但这种说法很可能是错误的。 :-)

但这是一种非常粗糙的方法，我不确定它是否在某些情况下会失败。这个问题还有其他（可能更优化）的解决方案吗？

Answer 1

如果它是完整二叉树，节点 x 的子节点为 2*x 和 2*x+1，那么有更快的方法

int get_bits(unsigned int x) {
  int high = 31;
  int low = 0,mid;
  while(high>=low) {
    mid = (high+low)/2;
    if(1<<mid==x)
      return mid+1;
    if(1<<mid<x) {
      low = mid+1;
    }
    else {
      high = mid-1;
    }
  }
  if(1<<mid>x)
    return mid;
  return mid+1;
}

unsigned int Common_Ancestor(unsigned int x,unsigned int y) {

  int xbits = get_bits(x);
  int ybits = get_bits(y);
  int diff,kbits;
  unsigned int k;
  if(xbits>ybits) {
    diff = xbits-ybits;
    x = x >> diff;
  }
  else if(xbits<ybits) {
    diff = ybits-xbits;
    y = y >> diff;
  }
  k = x^y;
  kbits = get_bits(k);
  return y>>kbits;  
}

它是如何工作的

1. 获取表示 x 所需的位y 使用二分查找的时间复杂度为 O(log(32))
2. x & 的二进制表示法的公共前缀y 是共同祖先
3. 以较大的位数表示的那个通过 k>> 变为相同的位。差异
4. k = x^y 消除 x & 的公共前缀y
5. 查找代表剩余后缀的位
6. 将 x 或 y 移动后缀位以获得公共前缀，即公共祖先。

这是有效的，因为基本上递归地将较大的数字除以二，直到两个数字相等。这个数字就是共同的祖先。除法实际上是右移运算。所以我们需要找到两个数字的共同前缀来找到最近的祖先

Answer 2

在 Scala 中，您可以：

  abstract class Tree
  case class Node(a:Int, left:Tree, right:Tree) extends Tree
  case class Leaf(a:Int) extends Tree

  def lca(tree:Tree, a:Int, b:Int):Tree = {
    tree match {
      case Node(ab,l,r) => {
        if(ab==a || ab ==b) tree else {
          val temp = lca(l,a,b);
          val temp2 = lca(r,a,b);
          if(temp!=null && temp2 !=null)
            tree
          else if (temp==null && temp2==null)
            null
          else if (temp==null) r else l
        }

      }
      case Leaf(ab) => if(ab==a || ab ==b) tree else null
    }
  }

Answer 3

两个节点 node1 和 node2 之间的最低公共祖先是树中两个节点都是后代的最低节点。

从根节点开始遍历二叉树，直到找到两个节点。每次访问节点时，都会将其添加到字典（称为parent）中。
一旦在二叉树中找到了两个节点，就可以使用字典获取node1的祖先并将其添加到一个集合中（称为祖先）。
对于node2，以相同的方式执行此步骤。如果node2的祖先存在于为node1设置的祖先中，则它是它们之间的第一个公共祖先。

下面是使用 stack 和 dictionary 实现的迭代 Python 解决方案，其中包含以下几点：

• 节点可以是其自身的后代
• 二进制文件中的所有节点树是唯一的
• node1和node2将存在于二叉树中

class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data  = data
        self.left  = left
        self.right = right

def lowest_common_ancestor(root, node1, node2):
    parent = {root: None}
    stack = [root]
    
    while node1 not in parent or node2 not in parent:
        node = stack[-1]
        stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)
    
    ancestors = set()
    while node1:
        ancestors.add(node1)
        node1 = parent[node1]
    while node2 not in ancestors:
        node2 = parent[node2]
    
    return node2.data

def main():
    '''
    Construct the below binary tree:

            30
           /  \
          /    \
         /      \
        11      29
       /  \    /  \
      8   12  25  14

    '''
    root = Node(30)
    root.left  = Node(11)
    root.right = Node(29)
    root.left.left  = Node(8)
    root.left.right = Node(12)
    root.right.left  = Node(25)
    root.right.right = Node(14)

    print(lowest_common_ancestor(root, root.left.left, root.left.right))       # 11
    print(lowest_common_ancestor(root, root.left.left, root.left))             # 11
    print(lowest_common_ancestor(root, root.left.left, root.right.right))      # 30


if __name__ == '__main__':
    main()

这种方法的复杂度是：O(n)

Answer 4

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        return left == null ? right : right == null ? left : root;
    }

Answer 5

这是 C++ 的实现方法。已尽力使算法尽可能易于理解：

// Assuming that `BinaryNode_t` has `getData()`, `getLeft()` and `getRight()`
class LowestCommonAncestor
{
  typedef char type;    
  // Data members which would behave as place holders
  const BinaryNode_t* m_pLCA;
  type m_Node1, m_Node2;

  static const unsigned int TOTAL_NODES = 2;

  // The core function which actually finds the LCA; It returns the number of nodes found
  // At any point of time if the number of nodes found are 2, then it updates the `m_pLCA` and once updated, we have found it!
  unsigned int Search (const BinaryNode_t* const pNode)
  {
    if(pNode == 0)
      return 0;

    unsigned int found = 0;

    found += (pNode->getData() == m_Node1);
    found += (pNode->getData() == m_Node2);

    found += Search(pNode->getLeft()); // below condition can be after this as well
    found += Search(pNode->getRight());

    if(found == TOTAL_NODES && m_pLCA == 0)
      m_pLCA = pNode;  // found !

    return found;
  }

public:
  // Interface method which will be called externally by the client
  const BinaryNode_t* Search (const BinaryNode_t* const pHead,
                              const type node1,
                              const type node2)
  {
    // Initialize the data members of the class
    m_Node1 = node1;
    m_Node2 = node2;
    m_pLCA = 0;

    // Find the LCA, populate to `m_pLCANode` and return
    (void) Search(pHead);
    return m_pLCA;
  }
};

如何使用它：

LowestCommonAncestor lca;
BinaryNode_t* pNode = lca.Search(pWhateverBinaryTreeNodeToBeginWith);
if(pNode != 0)
  ...

Answer 6

找到最低共同祖先的最简单方法是使用以下算法：

Examine root node

if value1 and value2 are strictly less that the value at the root node 
    Examine left subtree
else if value1 and value2 are strictly greater that the value at the root node 
    Examine right subtree
else
    return root

public int LCA(TreeNode root, int value 1, int value 2) {
    while (root != null) {
       if (value1 < root.data && value2 < root.data)
           return LCA(root.left, value1, value2);
       else if (value2 > root.data && value2 2 root.data)
           return LCA(root.right, value1, value2);
       else
           return root
    }

    return null;
} 

Answer 7

我找到了一个解决方案

1. Take inorder
2. Take preorder
3. Take postorder

根据 3 次遍历，就可以决定谁是 LCA。
从 LCA 找到两个节点的距离。
将这两个距离相加，就是答案。

Answer 8

这就是我的想法，

1. 找到第一个节点的路由，将其存储到 arr1 上。
2. 开始查找第 2 个节点的路由，同时检查从 root 到 arr1 的每个值。
3. 当值不同时，退出。旧匹配值是 LCA。

复杂性：
步骤 1 ： O(n) ，步骤 2 =~ O(n) ，总计 =~ O(n)。

Answer 9

以下是 c# (.net) 中的两种方法（均在上面讨论过）供参考：

1. 在二叉树中查找 LCA 的递归版本（O(N) - 最多访问每个节点）
   （解决方案的要点是 LCA 是二叉树中的唯一节点，其中两个元素都位于子树的两侧（左侧和右侧）是 LCA。(b) 而且无论哪一方存在哪个节点都并不重要 - 最初我试图保留该信息，显然递归函数在我意识到它后变得如此混乱，它变得非常优雅。

2. 。 (N))，并跟踪路径（使用额外的空间 - 因此，#1 可能更优越，即使二叉树平衡良好，空间可能可以忽略不计，因为额外的内存消耗将仅为 O(log(N ））。

   以便比较路径（本质上类似于接受的答案 - 但路径是通过假设指针节点不存在于二叉树节点中来计算的）

3. 只是为了完成（与问题无关），BST 中的 LCA (O(log(N))

4. 测试

递归：

private BinaryTreeNode LeastCommonAncestorUsingRecursion(BinaryTreeNode treeNode, 
            int e1, int e2)
        {
            Debug.Assert(e1 != e2);
            
            if(treeNode == null)
            {
                return null;
            }
            if((treeNode.Element == e1)
                || (treeNode.Element == e2))
            {
                //we don't care which element is present (e1 or e2), we just need to check 
                //if one of them is there
                return treeNode;
            }
            var nLeft = this.LeastCommonAncestorUsingRecursion(treeNode.Left, e1, e2);
            var nRight = this.LeastCommonAncestorUsingRecursion(treeNode.Right, e1, e2);
            if(nLeft != null && nRight != null)
            {
                //note that this condition will be true only at least common ancestor
                return treeNode;
            }
            else if(nLeft != null)
            {
                return nLeft;
            }
            else if(nRight != null)
            {
                return nRight;
            }
            return null;
        }

其中通过以下公共方法调用上述私有递归版本：

public BinaryTreeNode LeastCommonAncestorUsingRecursion(int e1, int e2)
        {
            var n = this.FindNode(this._root, e1);
            if(null == n)
            {
                throw new Exception("Element not found: " + e1);
            }
            if (e1 == e2)
            {   
                return n;
            }
            n = this.FindNode(this._root, e2);
            if (null == n)
            {
                throw new Exception("Element not found: " + e2);
            }
            var node = this.LeastCommonAncestorUsingRecursion(this._root, e1, e2);
            if (null == node)
            {
                throw new Exception(string.Format("Least common ancenstor not found for the given elements: {0},{1}", e1, e2));
            }
            return node;
        }

通过跟踪两个节点的路径解决方案：

public BinaryTreeNode LeastCommonAncestorUsingPaths(int e1, int e2)
        {
            var path1 = new List<BinaryTreeNode>();
            var node1 = this.FindNodeAndPath(this._root, e1, path1);
            if(node1 == null)
            {
                throw new Exception(string.Format("Element {0} is not found", e1));
            }
            if(e1 == e2)
            {
                return node1;
            }
            List<BinaryTreeNode> path2 = new List<BinaryTreeNode>();
            var node2 = this.FindNodeAndPath(this._root, e2, path2);
            if (node1 == null)
            {
                throw new Exception(string.Format("Element {0} is not found", e2));
            }
            BinaryTreeNode lca = null;
            Debug.Assert(path1[0] == this._root);
            Debug.Assert(path2[0] == this._root);
            int i = 0;
            while((i < path1.Count)
                && (i < path2.Count)
                && (path2[i] == path1[i]))
            {
                lca = path1[i];
                i++;
            }
            Debug.Assert(null != lca);
            return lca;
        }

其中FindNodeAndPath 定义为

private BinaryTreeNode FindNodeAndPath(BinaryTreeNode node, int e, List<BinaryTreeNode> path)
        {
            if(node == null)
            {
                return null;
            }
            if(node.Element == e)
            {
                path.Add(node);
                return node;
            }
            var n = this.FindNodeAndPath(node.Left, e, path);
            if(n == null)
            {
                n = this.FindNodeAndPath(node.Right, e, path);
            }
            if(n != null)
            {
                path.Insert(0, node);
                return n;
            }
            return null;
        }

BST (LCA) - 不相关（仅供参考）

public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2)
        {
            //ensure both elements are there in the bst
            var n1 = this.BstFind(e1, throwIfNotFound: true);
            if(e1 == e2)
            {
                return n1;
            }
            this.BstFind(e2, throwIfNotFound: true);
            BinaryTreeNode leastCommonAcncestor = this._root;
            var iterativeNode = this._root;
            while(iterativeNode != null)
            {
                if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2))
                {
                    iterativeNode = iterativeNode.Left;
                }
                else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2))
                {
                    iterativeNode = iterativeNode.Right;
                }
                else
                {
                    //i.e; either iterative node is equal to e1 or e2 or in between e1 and e2
                    return iterativeNode;
                }
            }
            //control will never come here
            return leastCommonAcncestor;
        }

单元测试

[TestMethod]
        public void LeastCommonAncestorTests()
        {
            int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
            int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22};
            BinarySearchTree bst = new BinarySearchTree();
            foreach (int e in a)
            {
                bst.Add(e);
                bst.Delete(e);
                bst.Add(e);
            }
            for(int i = 0; i < b.Length; i++)
            {
                var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]);
                Assert.IsTrue(n.Element == b[i]);
                var n1 = bst.LeastCommonAncestorUsingPaths(a[i], a[i + 1]);
                Assert.IsTrue(n1.Element == b[i]);
                Assert.IsTrue(n == n1);
                var n2 = bst.LeastCommonAncestorUsingRecursion(a[i], a[i + 1]);
                Assert.IsTrue(n2.Element == b[i]);
                Assert.IsTrue(n2 == n1);
                Assert.IsTrue(n2 == n);
            }
        }

Answer 10

如果有人对伪代码（用于大学家庭作业）感兴趣，这里就是其中之一。

GETLCA(BINARYTREE BT, NODE A, NODE  B)
IF Root==NIL
    return NIL
ENDIF

IF Root==A OR root==B
    return Root
ENDIF

Left = GETLCA (Root.Left, A, B)
Right = GETLCA (Root.Right, A, B)

IF Left! = NIL AND Right! = NIL
    return root
ELSEIF Left! = NIL
    Return Left
ELSE
    Return Right
ENDIF

Answer 11

虽然这个问题已经得到解答，但这是我使用 C 编程语言解决这个问题的方法。虽然代码显示了二叉搜索树（就 insert() 而言），但该算法也适用于二叉树。这个想法是在中序遍历中遍历从节点 A 到节点 B 的所有节点，在后序遍历中查找这些节点的索引。后序遍历中索引最大的节点是最低公共祖先。

这是一个有效的 C 代码，用于实现在二叉树中查找最低公共祖先的函数。我还提供了所有实用函数等，但请跳转到 CommonAncestor() 以快速理解。

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>

static inline int min (int a, int b)
{
    return ((a < b) ? a : b);
}
static inline int max (int a, int b)
{
    return ((a > b) ? a : b);
}

typedef struct node_ {
    int value;
    struct node_ * left;
    struct node_ * right;
} node;

#define MAX 12

int IN_ORDER[MAX] = {0};
int POST_ORDER[MAX] = {0};

createNode(int value) 
{
    node * temp_node = (node *)malloc(sizeof(node));
    temp_node->left = temp_node->right = NULL;
    temp_node->value = value;
    return temp_node;
}

node *
insert(node * root, int value)
{
    if (!root) {
        return createNode(value);
    }

    if (root->value > value) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }

    return root;
}


/* Builds inorder traversal path in the IN array */
void
inorder(node * root, int * IN)
{
    static int i = 0;

    if (!root) return;

    inorder(root->left, IN);
    IN[i] = root->value;
    i++;
    inorder(root->right, IN);
}

/* Builds post traversal path in the POST array */

void
postorder (node * root, int * POST)
{
    static int i = 0;

    if (!root) return;

    postorder(root->left, POST);
    postorder(root->right, POST);
    POST[i] = root->value;
    i++;
}


int
findIndex(int * A, int value)
{
    int i = 0;
    for(i = 0; i< MAX; i++) {
        if(A[i] == value) return i;
    }
}
int
CommonAncestor(int val1, int val2)
{
    int in_val1, in_val2;
    int post_val1, post_val2;
    int j=0, i = 0; int max_index = -1;

    in_val1 = findIndex(IN_ORDER, val1);
    in_val2 = findIndex(IN_ORDER, val2);
    post_val1 = findIndex(POST_ORDER, val1);
    post_val2 = findIndex(POST_ORDER, val2);

    for (i = min(in_val1, in_val2); i<= max(in_val1, in_val2); i++) {
        for(j = 0; j < MAX; j++) {
            if (IN_ORDER[i] == POST_ORDER[j]) {
                if (j > max_index) {
                    max_index = j;
                }
            }
        }
    }
    printf("\ncommon ancestor of %d and %d is %d\n", val1, val2, POST_ORDER[max_index]);
    return max_index;
}
int main()
{
    node * root = NULL; 

    /* Build a tree with following values */
    //40, 20, 10, 30, 5, 15, 25, 35, 1, 80, 60, 100
    root = insert(root, 40);
    insert(root, 20);
    insert(root, 10);
    insert(root, 30);
    insert(root, 5);
    insert(root, 15);
    insert(root, 25);
    insert(root, 35);
    insert(root, 1);
    insert(root, 80);
    insert(root, 60);
    insert(root, 100);

    /* Get IN_ORDER traversal in the array */
    inorder(root, IN_ORDER);

    /* Get post order traversal in the array */
    postorder(root, POST_ORDER);

    CommonAncestor(1, 100);


}

Answer 12

还可以有另一种方法。然而，它并不像答案中已经建议的那样有效。

• 为节点 n1 创建路径向量。

• 为节点 n2 创建第二个路径向量。

• 路径向量，表示从该节点将遍历以到达相关节点的集合节点。

  路径

• 比较两个路径向量。它们不匹配的索引，返回该索引处的节点 - 1。这将给出 LCA。

这种方法的缺点：

需要遍历树两次来计算路径向量。
需要额外的 O(h) 空间来存储路径向量。

然而，这也很容易实现和理解。

计算路径向量的代码：

private boolean findPathVector (TreeNode treeNode, int key, int pathVector[], int index) {

        if (treeNode == null) {
            return false;
        }

        pathVector [index++] = treeNode.getKey ();

        if (treeNode.getKey () == key) {
            return true;
        }
        if (findPathVector (treeNode.getLeftChild (), key, pathVector, index) || 
            findPathVector (treeNode.getRightChild(), key, pathVector, index)) {

            return true;        
        }

        pathVector [--index] = 0;
        return false;       
    }

Answer 13

尝试这样

node * lca(node * root, int v1,int v2)
{

if(!root) {
            return NULL;
    }
    if(root->data == v1 || root->data == v2) {
        return root;}
    else
    {
        if((v1 > root->data && v2 < root->data) || (v1 < root->data && v2 > root->data))
        {
            return root;
        }

        if(v1 < root->data && v2 < root->data)
        {
            root = lca(root->left, v1, v2);
        }

        if(v1 > root->data && v2 > root->data)
        {
            root = lca(root->right, v1, v2);
        }
    }
return root;
}

Answer 14

粗略方式：

• 在每个节点
  • X = 查找 n1、n2 中的任何一个是否存在于 Node 的左侧
  • Y = 查找 n1、n2 中的任何一个是否存在于节点的右侧
    • 如果节点本身是n1 || n2，我们可以将其称为左侧找到的
      或出于概括目的而正确。
  • 如果 X 和 Y 都为 true，则该节点就是 CA

上述方法的问题是我们将进行多次“查找”，即每个节点都有可能被遍历多次。
如果我们可以记录信息以便不再处理它，我们就可以克服这个问题（想想动态规划）。

因此，我们不是查找每个节点，而是记录已找到的内容。

更好的方法：

• 我们以深度优先的方式检查给定节点是否为 left_set（意味着在左子树中找到了 n1 | n2）或 right_set。 （注意：如果根本身是 n1 | n2，我们就赋予它为 left_set 的属性）
• 如果同时为 left_set 和 right_set，则该节点是 LCA。

代码：

struct Node *
findCA(struct Node *root, struct Node *n1, struct Node *n2, int *set) {
   int left_set, right_set;
   left_set = right_set = 0;
   struct Node *leftCA, *rightCA;
   leftCA = rightCA = NULL;

   if (root == NULL) {
      return NULL;
   }
   if (root == n1 || root == n2) {
      left_set = 1;
      if (n1 == n2) {
         right_set = 1;
      }
   }

   if(!left_set) {
      leftCA = findCA(root->left, n1, n2, &left_set);
      if (leftCA) {
         return leftCA;
      }
   }
   if (!right_set) {
      rightCA= findCA(root->right, n1, n2, &right_set);
      if(rightCA) {
         return rightCA;
      }
   }

   if (left_set && right_set) {
      return root;
   } else {
      *set = (left_set || right_set);
      return NULL;
   }
}

Answer 15

广度优先搜索的代码，以确保两个节点都在树中。
然后才能继续进行 LCA 搜索。
如果您有任何改进建议，请评论。
我认为我们可以将它们标记为已访问，并在我们停止的某个点重新开始搜索，以改进第二个节点（如果未找到已访问）

public class searchTree {
    static boolean v1=false,v2=false;
    public static boolean bfs(Treenode root, int value){
         if(root==null){
           return false;
     }
    Queue<Treenode> q1 = new LinkedList<Treenode>();

    q1.add(root);
    while(!q1.isEmpty())
    {
        Treenode temp = q1.peek();

        if(temp!=null) {
            q1.remove();
            if (temp.value == value) return true;
            if (temp.left != null) q1.add(temp.left);
            if (temp.right != null) q1.add(temp.right);
        }
    }
    return false;

}
public static Treenode lcaHelper(Treenode head, int x,int y){

    if(head==null){
        return null;
    }

    if(head.value == x || head.value ==y){
        if (head.value == y){
            v2 = true;
            return head;
        }
        else {
            v1 = true;
            return head;
        }
    }

    Treenode left = lcaHelper(head.left, x, y);
    Treenode right = lcaHelper(head.right,x,y);

    if(left!=null && right!=null){
        return head;
    }
    return (left!=null) ? left:right;
}

public static int lca(Treenode head, int h1, int h2) {
    v1 = bfs(head,h1);
    v2 = bfs(head,h2);
    if(v1 && v2){
        Treenode lca = lcaHelper(head,h1,h2);
        return lca.value;
    }
    return -1;
}
}

Answer 16

这里的一些解决方案假设存在对根节点的引用，一些假设树是 BST。
使用 hashmap 分享我的解决方案，不参考 root 节点，树可以是 BST 或非 BST：

    var leftParent : Node? = left
    var rightParent : Node? = right
    var map = [data : Node?]()

    while leftParent != nil {
        map[(leftParent?.data)!] = leftParent
        leftParent = leftParent?.parent
    }

    while rightParent != nil {
        if let common = map[(rightParent?.data)!] {
            return common
        }
        rightParent = rightParent?.parent
    }

Answer 17

解决方案 1：递归 - 更快

• 这个想法是从根开始遍历树。如果给定的密钥 p 和 q 中的任何一个与 root 匹配，则 root 是 LCA，假设两个密钥都存在。如果 root 与任何键都不匹配，我们将递归左子树和右子树。
• 左子树中存在一个键且右子树中存在另一个键的节点是 LCA。如果两个键都位于左子树，则左子树也有LCA，否则LCA位于右子树。

• 时间复杂度：O(n)
• 空间复杂度：O(h) - 对于递归调用堆栈

class Solution 
{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        if(root == null || root == p  || root == q)
            return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left == null)
            return right;
        else if(right == null)
            return left;
        else
            return root;    // If(left != null && right != null)
    }
}

解决方案 2：迭代 - 使用父指针 - 较慢

• 创建一个空哈希表。
• 将 p 及其所有祖先插入哈希表中。
• 检查哈希表中是否存在 q 或其任何祖先，如果是，则返回第一个现有祖先。

• 时间复杂度：O(n) - 在最坏的情况下，我们可能会访问二叉树的所有节点。
• 空间复杂度：O(n) - 使用父指针哈希表、祖先集和队列的空间各为 O(n)。

class Solution
{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        HashMap<TreeNode, TreeNode> parent_map = new HashMap<>();
        HashSet<TreeNode> ancestors_set = new HashSet<>();
        Queue<TreeNode> queue = new LinkedList<>();

        parent_map.put(root, null);
        queue.add(root);

        while(!parent_map.containsKey(p) || !parent_map.containsKey(q))
        {
            TreeNode node = queue.poll();

            if(node.left != null)
            {
                parent_map.put(node.left, node);
                queue.add(node.left);
            }
            if(node.right != null)
            {
                parent_map.put(node.right, node);
                queue.add(node.right);
            }
        }

        while(p != null)
        {
            ancestors_set.add(p);
            p = parent_map.get(p);
        }

        while(!ancestors_set.contains(q))
            q = parent_map.get(q);

        return q;
    }
}

Answer 18

从root节点开始向下移动，如果您找到任何将p或q作为其直接子节点的节点，那么它就是LCA。 （编辑 - 这应该是如果 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;
                }
        }
}

实际代码

Answer 19

Nick Johnson 是正确的，如果没有父指针，O(n) 时间复杂度算法是最好的算法。）有关该算法的简单递归版本，请参阅 Kinding 的帖子，运行时间为 O(n)。

但请记住，如果您的节点有父指针，则可以使用改进的算法。对于所讨论的两个节点，通过从节点开始并在前面插入父节点来构造一个包含从根到该节点的路径的列表。

因此，对于示例中的 8，您将得到（显示步骤）： {4}, {2, 4}, {1, 2, 4}

对相关的其他节点执行相同的操作，结果是（未显示步骤）： { 1, 2}

现在比较您创建的两个列表，查找列表中不同的第一个元素，或其中一个列表的最后一个元素，以先到者为准。

该算法需要 O(h) 时间，其中 h 是树的高度。在最坏的情况下，O(h) 相当于 O(n)，但如果树是平衡的，则仅为 O(log(n))。它还需要 O(h) 空间。可以使用仅使用恒定空间的改进版本，代码显示在 CEGRD 的帖子中，

---

无论树是如何构建的，如果这将是您在树上执行多次而无需在其间进行更改的操作，您可以使用其他需要 O(n) [线性] 时间准备的算法，但找到任何对只需要 O(1) [常量] 时间。有关这些算法的参考，请参阅 Wikipedia 上的最低共同祖先问题页面。 （感谢 Jason 最初发布此链接）

Answer 20

这是JAVA中的工作代码

public static Node LCA(Node root, Node a, Node b) {
   if (root == null) {
       return null;
   }

   // If the root is one of a or b, then it is the LCA
   if (root == a || root == b) {
       return root;
   }

   Node left = LCA(root.left, a, b);
   Node right = LCA(root.right, a, b);

   // If both nodes lie in left or right then their LCA is in left or right,
   // Otherwise root is their LCA
   if (left != null && right != null) {
      return root;
   }

   return (left != null) ? left : right; 
}

Answer 21

到目前为止给出的答案使用递归或存储，例如内存中的路径。

如果树很深，这两种方法都可能会失败。

这是我对这个问题的看法。
当我们检查两个节点的深度（距根的距离）时，如果它们相等，那么我们可以安全地从两个节点向上移动到共同祖先。如果其中一个深度较大，那么我们应该从更深的节点向上移动，同时停留在另一个节点上。

代码如下：

findLowestCommonAncestor(v,w):
  depth_vv = depth(v);
  depth_ww = depth(w);

  vv = v; 
  ww = w;

  while( depth_vv != depth_ww ) {
    if ( depth_vv > depth_ww ) {
      vv = parent(vv);
      depth_vv--;
    else {
      ww = parent(ww);
      depth_ww--;
    }
  }

  while( vv != ww ) {
    vv = parent(vv);
    ww = parent(ww);
  }

  return vv;    

该算法的时间复杂度为：O(n)。
该算法的空间复杂度为：O(1)。

关于深度的计算，我们可以先记住定义：如果v是根，则深度(v) = 0；否则，深度(v) = 深度(parent(v)) + 1。我们可以按如下方式计算深度：

depth(v):
  int d = 0;
  vv = v;
  while ( vv is not root ) {
    vv = parent(vv);
    d++;
  }
  return d;

Answer 22

嗯，这取决于二叉树的结构。假设您有某种方法可以在给定树根的情况下找到所需的叶节点 - 只需将其应用于两个值，直到您选择的分支发散。

如果您没有办法在给定根的情况下找到所需的叶子，那么您唯一的解决方案 - 无论是在正常操作中还是找到最后一个公共节点 - 都是对树进行强力搜索。

Answer 23

这可以在以下位置找到：-
http://goursaha.freeoda.com/DataStructure/LowestCommonAncestor.html

 tree_node_type *LowestCommonAncestor(
 tree_node_type *root , tree_node_type *p , tree_node_type *q)
 {
     tree_node_type *l , *r , *temp;
     if(root==NULL)
     {
        return NULL;
     }

    if(root->left==p || root->left==q || root->right ==p || root->right ==q)
    {
        return root;
    }
    else
    {
        l=LowestCommonAncestor(root->left , p , q);
        r=LowestCommonAncestor(root->right , p, q);

        if(l!=NULL && r!=NULL)
        {
            return root;
        }
        else
        {
        temp = (l!=NULL)?l:r;
        return temp;
        }
    }
}

Answer 24

Tarjan 的离线最不常见祖先算法 已经足够好了（参见维基百科）。 维基百科上有更多关于这个问题（最低共同祖先问题）的信息。

Answer 25

要找出两个节点的共同祖先： -

• 使用二分搜索在树中查找给定节点 Node1 并将在此过程中访问的所有节点保存在数组中（例如 A1）。时间 - O(logn)，空间 - O(logn)
• 使用二分搜索在树中找到给定的 Node2，并将此过程中访问的所有节点保存在数组中，例如 A2。时间 - O(logn)，空间 - O(logn)
• 如果 A1 列表或 A2 列表为空，则该节点不存在，因此没有共同祖先。
• 如果A1列表和A2列表非空，则查找列表，直到找到不匹配的节点。一旦找到这样的节点，那么该节点之前的节点就是共同祖先。

这适用于二叉搜索树。

Answer 26

我尝试使用Java中的说明性图片和工作代码，

http://tech.bragboy.com/2010/02/least-common-ancestor-without-using.html

Answer 27

对于平衡二叉树，下面的递归算法将以 O(log N) 运行。如果传入 getLCA() 函数的任何一个节点与根相同，则根将是 LCA，并且不需要执行任何递归。

测试用例。
[1] 两个节点 n1 和 n1 n2 在树中并位于其父节点的两侧。
[2] 节点 n1 或 n2 为根，LCA 为根。
[3]树中只有n1或n2，LCA将是树根的左子树的根节点，或者LCA将是树的右子树的根节点根。

[4] n1 和 n2 都不在树中，没有 LCA。
[5] n1 和 n2 彼此相邻在一条直线上，LCA 将是靠近树根的 n1 或 n2 中的一个。

//find the search node below root
bool findNode(node* root, node* search)
{
    //base case
    if(root == NULL)
        return false;

    if(root->val == search->val)
        return true;

    //search for the node in the left and right subtrees, if found in either return true
    return (findNode(root->left, search) || findNode(root->right, search));
}

//returns the LCA, n1 & n2 are the 2 nodes for which we are
//establishing the LCA for
node* getLCA(node* root, node* n1, node* n2)
{
    //base case
    if(root == NULL)
        return NULL;

    //If 1 of the nodes is the root then the root is the LCA
    //no need to recurse.
    if(n1 == root || n2 == root)
        return root;

    //check on which side of the root n1 and n2 reside
    bool n1OnLeft = findNode(root->left, n1);
    bool n2OnLeft = findNode(root->left, n2);

    //n1 & n2 are on different sides of the root, so root is the LCA
    if(n1OnLeft != n2OnLeft)
        return root;

    //if both n1 & n2 are on the left of the root traverse left sub tree only
    //to find the node where n1 & n2 diverge otherwise traverse right subtree
    if(n1OnLeft)
        return getLCA(root->left, n1, n2);
    else
        return getLCA(root->right, n1, n2);
}

Answer 28

只要从整个树的根向下走，只要必须找到祖先的两个给定节点，例如p和q，都是在同一子树中（意味着它们的值都小于或都大于根的值）。

它直接从根部走到最不常见的祖先，而不看树的其余部分，所以它几乎是尽可能快的。有几种方法可以做到这一点。

迭代，O(1) 空间

<块引用>

Python

def lowestCommonAncestor(self, root, p, q):
    while (root.val - p.val) * (root.val - q.val) > 0:
        root = (root.left, root.right)[p.val > root.val]
    return root

<块引用>

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while ((root.val - p.val) * (root.val - q.val) > 0)
        root = p.val < root.val ? root.left : root.right;
    return root;
}

如果发生溢出，我会这样做 (root.val - (long)p.val) * (root.val - (long)q.val)

递归

<块引用>

Python

def lowestCommonAncestor(self, root, p, q):
    next = p.val < root.val > q.val and root.left or \
           p.val > root.val < q.val and root.right
    return self.lowestCommonAncestor(next, p, q) if next else root

<块引用>

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    return (root.val - p.val) * (root.val - q.val) < 1 ? root :
           lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
}

Answer 29

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

Answer 30

考虑这棵树

如果我们进行后序和前序遍历并找到第一个出现的共同前驱和后继，我们得到共同的祖先。

后序 => 0,2,1,5,4,6,3,8,10,11,9,14,15,13,​​12,7
预购 => 7,3,1,0,2,6,4,5,12,9,8,11,10,13,15,14

• 例如：1

后序中8,11 的最小共同祖先

=>9， 8 和 14,15,13,​​12,7 之后11
在预购中，我们在 8 和 之前有 =>7,3,1,0,2,6,4,5,12,9 11

9 是 8& 后面出现的第一个常见数字。后序中的 11 和 8 点之前前序为 11，因此 9 是答案

• 例如：2

5,10 11,9,14,15,13,​​12,7 的最小共同祖先

后序中
前序中的 7,3,1,0,2,6,4

7 是后序中 5,10 之后、前序中 5,10 之前出现的第一个数字，因此 7 是答案