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

小开

Tarjan 的离线最小公共祖先算法已经足够好了(参考维基百科)。有更多关于这个问题(最近公共祖先问题)的信息。

小开

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

如果你没有办法找到你想要的叶子，那么你唯一的解决方案——无论是在正常操作还是找到最后一个公共节点——就是树的暴力搜索法。

小开

最佳答案

Nick Johnson 说得对，如果没有父指针，那么 O (n)时间复杂度算法是最佳选择。)有关该算法的简单递归版本，请参见在 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)[常数]时间。有关这些算法的参考资料，请参阅维基百科的最近公共祖先问题页面。(感谢 Jason 最初发布这个链接)

小开

我已经尝试使用 Java 中的示例图片和工作代码,

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

小开

你可浏览以下网址:- 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;
}
}
}

小开

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

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

这对二叉查找树有用。

小开

从 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;
}
}
}

行动守则

小开

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

如果您的树非常深，这两种方法都可能失败。

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

密码如下:

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) = 深度(父(v)) + 1。我们可以计算深度如下:

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

小开

下面是 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;
}

小开

在 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
}
}

小开

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
}

小开

下面是 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)
...

小开

Php 的密码。我假设这个树是一个 Array 二叉树。因此，您甚至不需要树来计算 LCA。 Input: 两个节点的索引产出: 生命周期评价指数

    <?php
global $Ps;


function parents($l,$Ps)
{


if($l % 2 ==0)
$p = ($l-2)/2;
else
$p = ($l-1)/2;


array_push($Ps,$p);
if($p !=0)
parents($p,$Ps);


return $Ps;
}
function lca($n,$m)
{
$LCA = 0;
$arr1 = array();
$arr2 = array();
unset($Ps);
$Ps = array_fill(0,1,0);
$arr1 = parents($n,$arr1);
unset($Ps);
$Ps = array_fill(0,1,0);
$arr2 = parents($m,$arr2);


if(count($arr1) > count($arr2))
$limit = count($arr2);
else
$limit = count($arr1);


for($i =0;$i<$limit;$i++)
{
if($arr1[$i] == $arr2[$i])
{
$LCA = $arr1[$i];
break;
}
}
return $LCA;//this is the index of the element in the tree


}


var_dump(lca(5,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;
}

小开

我找到了解决办法

按顺序来
请预订
带上订单

根据3次遍历，您可以决定谁是 LCA。从 LCA 查找两个节点的距离。把这两个距离加起来，这就是答案。

小开

public class LeastCommonAncestor {


private TreeNode root;


private static class TreeNode {
TreeNode left;
TreeNode right;
int item;


TreeNode (TreeNode left, TreeNode right, int item) {
this.left = left;
this.right = right;
this.item = item;
}
}


public void createBinaryTree (Integer[] arr) {
if (arr == null)  {
throw new NullPointerException("The input array is null.");
}


root = new TreeNode(null, null, arr[0]);


final Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);


final int half = arr.length / 2;


for (int i = 0; i < half; i++) {
if (arr[i] != null) {
final TreeNode current = queue.poll();
final int left = 2 * i + 1;
final int right = 2 * i + 2;


if (arr[left] != null) {
current.left = new TreeNode(null, null, arr[left]);
queue.add(current.left);
}
if (right < arr.length && arr[right] != null) {
current.right = new TreeNode(null, null, arr[right]);
queue.add(current.right);
}
}
}
}


private static class LCAData {
TreeNode lca;
int count;


public LCAData(TreeNode parent, int count) {
this.lca = parent;
this.count = count;
}
}




public int leastCommonAncestor(int n1, int n2) {
if (root == null) {
throw new NoSuchElementException("The tree is empty.");
}


LCAData lcaData = new LCAData(null, 0);
// foundMatch (root, lcaData, n1,  n2);


/**
* QQ: boolean was returned but never used by caller.
*/
foundMatchAndDuplicate (root, lcaData, n1,  n2, new HashSet<Integer>());


if (lcaData.lca != null) {
return lcaData.lca.item;
} else {
/**
* QQ: Illegal thrown after processing function.
*/
throw new IllegalArgumentException("The tree does not contain either one or more of input data. ");
}
}


//    /**
//     * Duplicate n1, n1         Duplicate in Tree
//     *      x                           x               => succeeds
//     *      x                           1               => fails.
//     *      1                           x               => succeeds by throwing exception
//     *      1                           1               => succeeds
//     */
//    private boolean foundMatch (TreeNode node, LCAData lcaData, int n1, int n2) {
//        if (node == null) {
//            return false;
//        }
//
//        if (lcaData.count == 2) {
//            return false;
//        }
//
//        if ((node.item == n1 || node.item == n2) && lcaData.count == 1) {
//            lcaData.count++;
//            return true;
//        }
//
//        boolean foundInCurrent = false;
//        if (node.item == n1 || node.item == n2) {
//            lcaData.count++;
//            foundInCurrent = true;
//        }
//
//        boolean foundInLeft = foundMatch(node.left, lcaData, n1, n2);
//        boolean foundInRight = foundMatch(node.right, lcaData, n1, n2);
//
//        if ((foundInLeft && foundInRight) || (foundInCurrent && foundInRight) || (foundInCurrent && foundInLeft)) {
//            lcaData.lca = node;
//            return true;
//        }
//        return foundInCurrent || (foundInLeft || foundInRight);
//    }




private boolean foundMatchAndDuplicate (TreeNode node, LCAData lcaData, int n1, int n2, Set<Integer> set) {
if (node == null) {
return false;
}


// when both were found
if (lcaData.count == 2) {
return false;
}


// when only one of them is found
if ((node.item == n1 || node.item == n2) && lcaData.count == 1) {
if (!set.contains(node.item)) {
lcaData.count++;
return true;
}
}


boolean foundInCurrent = false;
// when nothing was found (count == 0), or a duplicate was found (count == 1)
if (node.item == n1 || node.item == n2) {
if (!set.contains(node.item)) {
set.add(node.item);
lcaData.count++;
}
foundInCurrent = true;
}


boolean foundInLeft = foundMatchAndDuplicate(node.left, lcaData, n1, n2, set);
boolean foundInRight = foundMatchAndDuplicate(node.right, lcaData, n1, n2, set);


if (((foundInLeft && foundInRight) ||
(foundInCurrent && foundInRight) ||
(foundInCurrent && foundInLeft)) &&
lcaData.lca == null) {
lcaData.lca = node;
return true;
}
return foundInCurrent || (foundInLeft || foundInRight);
}








public static void main(String args[]) {
/**
* Binary tree with unique values.
*/
Integer[] arr1 = {1, 2, 3, 4, null, 6, 7, 8, null, null, null, null, 9};
LeastCommonAncestor commonAncestor = new LeastCommonAncestor();
commonAncestor.createBinaryTree(arr1);


int ancestor = commonAncestor.leastCommonAncestor(2, 4);
System.out.println("Expected 2, actual " + ancestor);


ancestor = commonAncestor.leastCommonAncestor(2, 7);
System.out.println("Expected 1, actual " +ancestor);


ancestor = commonAncestor.leastCommonAncestor(2, 6);
System.out.println("Expected 1, actual " + ancestor);


ancestor = commonAncestor.leastCommonAncestor(2, 1);
System.out.println("Expected 1, actual " +ancestor);


ancestor = commonAncestor.leastCommonAncestor(3, 8);
System.out.println("Expected 1, actual " +ancestor);


ancestor = commonAncestor.leastCommonAncestor(7, 9);
System.out.println("Expected 3, actual " +ancestor);


// duplicate request
try {
ancestor = commonAncestor.leastCommonAncestor(7, 7);
} catch (Exception e) {
System.out.println("expected exception");
}


/**
* Binary tree with duplicate values.
*/
Integer[] arr2 = {1, 2, 8, 4, null, 6, 7, 8, null, null, null, null, 9};
commonAncestor = new LeastCommonAncestor();
commonAncestor.createBinaryTree(arr2);


// duplicate requested
ancestor = commonAncestor.leastCommonAncestor(8, 8);
System.out.println("Expected 1, actual " + ancestor);


ancestor = commonAncestor.leastCommonAncestor(4, 8);
System.out.println("Expected 4, actual " +ancestor);


ancestor = commonAncestor.leastCommonAncestor(7, 8);
System.out.println("Expected 8, actual " +ancestor);


ancestor = commonAncestor.leastCommonAncestor(2, 6);
System.out.println("Expected 1, actual " + ancestor);


ancestor = commonAncestor.leastCommonAncestor(8, 9);
System.out.println("Expected 8, actual " +ancestor); // failed.
}
}

小开

考虑这个树 < img src = “ https://i.stack.imgur.com/8ohuz.jpg”alt = “ enter image description here”>

如果我们做后序和预序遍历，并找到第一个出现的公共前辈和后继者，我们就得到了公共祖先。

Postorder = > 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,14,15,13,12,7在8和11之后在8 & 11之前，我们有 = > 7,3,1,0,2,6,4,5,12,9

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是答案

小开

我是这么想的,

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

复杂性: 步骤1: O (n) ，步骤2 = ~ O (n) ，total = ~ O (n)。

小开

如果它是完整的二叉树，并且节点 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;
}

它是怎么工作的

获取表示 x & y 所需的位，使用二进制搜索是 O (log (32))

二进制表示法的共同前缀是 x & y 的共同祖先

以较大的比特数表示的任意一个比特数，通过 k > > diff 表示为相同的比特数

K = x ^ y 消去 x & y 的公共前缀

查找表示剩余后缀的位

通过后缀位移动 x 或 y 来获得共同的前缀，这是共同的祖先。

这种方法是有效的，因为基本上是递归地将较大的数除以两，直到两个数相等。这个数字是共同的祖先。划分是有效的正确转移操作。所以我们需要找到两个数字的共同前缀来找到最近的祖先

小开

下面是 c # (. net)中的两种方法(上面都讨论过) ，以供参考:

在二叉树中查找 LCA 的递归版本(O (N)-最多访问每个节点) (解决方案的要点是 LCA 是二叉树中仅有的 (a)节点，其中两个元素分别驻留在子树的两边(左边和右边)。而且不管哪个节点出现在哪一边-最初我试图保留这个信息，显然递归函数变得非常混乱。当我意识到的时候，它变得非常优雅。
搜索两个节点(O (N)) ，并保持路径跟踪(使用额外的空间-所以，# 1可能是优越的，即使空间可能是可忽略的，如果二叉树是很好的平衡，那么额外的内存消耗将只是在 O (log (N))。

这样就可以对路径进行比较(本质上类似于已接受的答案——但是路径是通过假设二叉树节点中没有指针节点来计算的)
只是为了完成(与问题无关) ，LCA 在 BST (O (log (N))
测试

递归:

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);
}
}

小开

如果有人对伪代码感兴趣(用于大学的家庭作业) ，这里就有一个。

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

小开

//如果两个值都小于当前节点，则遍历左侧子树 //或者，如果两个值都大于当前节点，则遍历右侧子树 //或 LCA 是当前节点

public BSTNode findLowestCommonAncestor(BSTNode currentRoot, int a, int b){
BSTNode commonAncestor = null;
if (currentRoot == null) {
System.out.println("The Tree does not exist");
return null;
}


int currentNodeValue = currentRoot.getValue();
//If both the values are less than the current node then traverse the left subtree
//Or If both the values are greater than the current node then traverse the right subtree
//Or LCA is the current node
if (a < currentNodeValue && b < currentNodeValue) {
commonAncestor = findLowestCommonAncestor(currentRoot.getLeft(), a, b);
} else if (a > currentNodeValue && b > currentNodeValue) {
commonAncestor = findLowestCommonAncestor(currentRoot.getRight(), a, b);
} else {
commonAncestor = currentRoot;
}


return commonAncestor;
}

小开

下面的递归算法将以 O (logn)表示一个平衡二叉搜索树。如果传递到 getLCA ()函数中的任何一个节点与根节点相同，那么根节点就是 LCA，不需要执行任何回调操作。

测试案例。 [1] 两个节点 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);
}

小开

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

这是一个工作的 C 代码，用来实现一个在二叉树中查找最近公共祖先的函数。我也提供了所有的实用程序功能等，但是为了快速理解，请跳转到 CommonSung ()。

#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);




}

小开

还可以有另一种方法，但这种方法没有答案中已经建议的方法那么有效。

为节点 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;
}

小开

试试这样

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;
}

小开

粗制滥造:

每个节点
- X = find 如果 n1和 n2中的任何一个存在于 Node 的左侧
- Y = find 如果 n1和 n2中的任何一个存在于 Node 的右侧
  - 如果节点本身是 n1 | | n2，我们可以在左侧调用它或权利为了概括的目的。
- 如果 X 和 Y 都为真，那么 Node 就是 CA

上述方法的问题在于，我们将多次执行“查找”操作，也就是说，每个节点都有可能被多次遍历。我们可以克服这个问题，如果我们可以记录的信息，以便不再处理它(想想动态编程)。

因此，我们不需要找到每个节点，而是记录已经找到的节点。

更好的方法:

我们检查给定节点是 left _ set (意味着在左侧子树中找到了 n1 | n2)还是 right _ set (以深度优先的方式)。(注意: 如果根本身是 n1 | n2，那么它的属性是 left _ set)
如果 left _ set 和 right _ set 都是 LCA，则节点是 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;
}
}

小开

只要两个给定的节点(比如说 p和 q，必须找到始祖)都在同一个子树中，就可以从整个树的 root向下走(这意味着它们的值都小于或者都大于 root)。

它直接从根走到最小共同祖先，而不是看树的其余部分，所以它几乎是最快的。有几种方法。

迭代，O (1)空间

巨蟒

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

爪哇咖啡

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)

递归的

巨蟒

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

爪哇咖啡

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);
}

小开

一个广度优先搜索的代码，以确保两个节点都在树中。只有这样才能继续进行 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;
}
}

小开

这里的一些解决方案假设有对根节点的引用，一些解决方案假设树是 BST。使用散列表共享我的解决方案，没有参考 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
}

小开

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;
}

小开

解决方案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;
}
}

小开

以下是实现解决这个问题的最快方法。空间复杂度 O (1) ，时间复杂度 O (n)。如果

如果一个节点的左右值都不为空，则该节点为你的答案(第三个“如果”从上)。当迭代如果一个值被发现，作为所有的价值都是唯一的，必须存在，我们不需要搜索它的后代。所以只需返回找到的匹配的节点节点的左侧和右侧分支内容空传播空当达到顶级递归时，如果有一个分支返回值时，其他值不会继续传播该值返回当前节点。如果它达到根级递归一个为空，另一个为非空，返回非空值，作为问题, 保证值存在时，它必须在找到了我们从来没有遍历过的节点。

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

小开

两个节点 node1和 node2之间的最近公共祖先是同时有两个节点作为后代的树中最低的节点。

从根节点遍历二叉树，直到找到两个节点。每次访问一个节点，它就被添加到一个字典(称为 parent)中。一旦在二叉树中找到这两个节点，就可以使用字典获取 node1的祖先，并将其添加到集合中(称为 ancestors)。对于 node2，以相同的方式执行此步骤。如果 node2的祖先存在于 node1的祖先集中，那么它就是它们之间的第一个共同祖先。

下面是使用栈和字典实现的迭代 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)