这里的二叉树不一定是二叉搜索树。
可以将其结构表示为 -
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），因为它们仅是数组中的简单迭代）。但很有可能我错了。:-)
但这只是一个非常粗略的方法，我不确定是否有一些情况会失效。还有其他（可能更优）的解决方案吗？
编写广度优先搜索的代码，以确保树中同时包含两个节点。 仅在此条件成立后继续进行LCA搜索。 如果您有任何改进建议，请留言评论。 我认为我们可以将它们标记为已访问，并在离开时重新启动搜索，以改进对第二个节点的搜索（如果未找到VISITED）。
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;
}
}
这是我认为的：
复杂度： 步骤1：O（n），步骤2 =~ O（n），总计=〜O（n）。
我找到了一个解决方案
根据三种遍历方式，您可以确定谁是LCA。 从LCA找到两个节点的距离。 将这两个距离相加，得出答案。
找到最近公共祖先的最简单方法是使用以下算法：
检查根节点
如果value1和value2严格小于根节点的值 检查左子树 否则，如果value1和value2严格大于根节点的值 检查右子树 否则 返回根节点
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;
}
如果有人对伪代码（用于大学作业）感兴趣，这里有一个。
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
以下是两种在c# (.net)中的方法（上面都有讨论）供参考：
在二叉树中找到LCA的递归版本（O(N) - 最多每个节点都会被访问） 解决方案的主要点是LCA是(a) 二叉树中仅有的一个节点，其中两个元素分别位于子树（左侧和右侧）的一侧。 (b) 并且无论哪个节点位于哪一侧都没有关系 - 最初我尝试保留这些信息，但显然递归函数变得非常混乱。一旦我意识到这一点，它就变得非常优雅。
搜索两个节点（O(N)），并跟踪路径（使用额外空间 - 因此，如果二叉树平衡良好，则#1可能更优，即使空间可能可以忽略不计，因为额外的内存消耗将只是O(log(N))）。 因此，路径被比较（基本上类似于接受的答案 - 但路径是通过假定指针节点不存在于二叉树节点中来计算的）
仅为完整性而提供（与问题无关），BST中的LCA（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);
}
}
这是用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)
...
试试这样
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;
}
还有一种方法，但它不如答案中已经建议的那种方法高效。
为节点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;
}
以下是解决此问题的最快方法（链接1）。空间复杂度为O(1)，时间复杂度为O(n)。如果
如果一个节点的左右值都不为空，则该节点是您的答案（从顶部开始的第3个“if”）。在迭代时，如果找到一个值，由于所有值都是唯一的且必须存在，因此我们不需要搜索其后代。因此，只需返回匹配的已找到节点即可。如果一个节点的左右分支内容为空，则向上传播null。当达到顶级递归时，如果一个分支返回值，则其他分支不会继续传播该值，当两个分支都返回非null时，返回当前节点。如果它以一个null和另一个非null的值到达根级递归，则返回非null值，因为问题承诺该值存在，它必须在我们从未遍历的找到节点的子树中。
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);
}
}
