二叉树这里不一定是二叉搜索树。
该结构可作为 -
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的共同祖先，然后我们做所有这一切都在序树的遍历，在这种情况下，恰好是[4,9 8和5之间的节点列表，2]。 然后我们检查哪个节点在此列表中最后出现在后序遍历，它是2。因此，共同的祖先为8和5是2。
在这个算法的复杂性，我认为这是（为序/后序遍历，中其余的步骤重新为O（N），因为它们只不过是简单的迭代更加阵列为O（n））O（N）。 但是有一个很大的机会，这是错误的。 :-)
但是，这是一个非常粗糙的方法，我不知道，如果它打破了一些情况。 是否有任何其他（可能更优）解决这个问题？
尼克·约翰逊是正确的，一个一个O（n）的时间复杂度算法是最好的，如果你没有父指针，你可以做。）对于算法的一个简单的递归版本中看到代码金丁的职务它运行在O（n）的时间。
但请记住，如果您的节点有父指针，改进的算法是可行的。 对于所讨论的两个节点构造通过启动在节点和前插入母体含有从根到节点的路径的列表。
所以对于你的例子8，你（显示步骤）：{4}，{2,4}，{1，2，4}
执行相同的问题的其它节点，从而产生（未示出的步骤）：{1,2}
现在比较两个列表中你做想找一份名单不同的第一个元素，或者其中一个列表的最后一个元素，以先到者为准。
该算法需要O（H）时间，其中h是树的高度。 在最坏的情况下，O（h）为相当于O（n）的，但如果树是平衡的，即只有O（日志（N））。 它也需要O（H）的空间。 一种改进版本可能使用唯一不变的空间，代码所示CEGRD的帖子
无论树的构建，如果这将是您对树而不改变它之间执行许多次的操作中，有可以使用需要O（n）的[线性]时间制备其它算法，但随后发现的任何对只需要O（1）[常数]的时间。 对于这些算法的引用，请参阅最低的共同祖先问题页维基百科 。 （感谢贾森最初发布此链接）
从开始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;
}
}
}
代码在行动
这里是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;
}
目前给出的答案使用递归或专卖店，例如，在内存的路径。
如果你有一个非常深树这两种方法可能会失败。
这是我对这个问题的。 当我们检查两个节点的深度（从根部的距离），如果它们相等，那么我们可以安全地从向上朝向共同的祖先两个节点移动。 如果深度的一次规模更大，那么我们就应该从向上更深节点停留在另一个而移动。
下面是代码：
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;
那么，这样的取决于你的二叉树是如何构成的。 想必你找到给出的树的根所需的叶节点的一些方式 - 简单的应用，为两个值，直到您选择岔开的树枝。
如果你没有办法找到给出的根，那么你唯一的解决方案所需的叶 - 无论是在正常运行，并找到最后的共同节点 - 是一个强力搜索树。
这可以在这里找到： - 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;
}
}
}
的Tarjan的离线至少共同祖先的算法是足够好（也可参见维基百科 ）。 还有更多关于这个问题（最低的共同祖先的问题）， 维基百科 。
要了解双节点的共同祖先： -
这将工作二叉搜索树。
我已经在Java中使用的图片说明，试图和工作代码，
http://tech.bragboy.com/2010/02/least-common-ancestor-without-using.html
下面的递归算法会为O（log N）的平衡二叉树运行。 如果任一传入getLCA（）函数的节点的是相同的根，则根将是LCA会有不需要执行任何recussrion。
测试用例。 [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);
}
刚刚从整个树的走root只要双方给出的节点，说p和q ，为此祖代被发现，在相同的子树（这意味着他们的值都小于或都比根的大）。
这走直接从根到最小共同祖先，不看树的其余部分，因此它是非常快，因为它得到。 有几个方法可以做到这一点。
迭代，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
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 - （长）p.val）*（root.val - （长）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
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);
}
在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
}
考虑这棵树
如果我们这样做后序和序遍历，并找到第一个发生的历史共同的前任和继任者，我们得到的共同祖先。
邮购=> 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
8,11的最共同的祖先
在后序，我们有=> 9,14,15,13,12,7在预订8 11后，我们有=> 7,3,1,0,2,6,4,5,12,9 8 11之前
图9是在后序8 11后发生的第一公共数和序8 11之前，因此，图9是该答案
5,10最小的共同祖先
11,9,14,15,13,12,7在序后序7,3,1,0,2,6,4
图7是在后序5,10和5,10前序中后发生的第一个数字，因此，图7是该答案
如果是与节点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（日志（32））
- X和Y的二进制符号的共同前缀是共同的祖先
- 取其由较大的无位由k赞助商相同的位>>差异表示
- K =的x ^ýerazes X和Y的共同前缀
- 找到代表剩余后缀位
- 通过后缀个位移x或y来获得公共前缀这是共同的祖先。
这工作，因为由两个基本除以数量较大递归，直到两个数是相等的。 这个数字是共同的祖先。 划分实际上是右移opearation。 因此，我们需要找到两个数字的公共前缀查找最近的祖先
这是做它的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)
...
找到最低的共同祖先的最简单方法是使用下面的算法：
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找到两个节点的距离。 加入这两个距离，这就是答案。
这里是我的想法，
复杂性：步骤1：O（N），步骤2 =〜O（n）的总=〜O（N）。
Here are two approaches in c# (.net) (both discussed above) for reference:
Recursive version of finding LCA in binary tree (O(N) - as at most each node is visited) (main points of the solution is LCA is (a) only node in binary tree where both elements reside either side of the subtrees (left and right) is LCA. (b) And also it doesn't matter which node is present either side - initially i tried to keep that info, and obviously the recursive function become so confusing. once i realized it, it became very elegant.
Searching both nodes (O(N)), and keeping track of paths (uses extra space - so, #1 is probably superior even thought the space is probably negligible if the binary tree is well balanced as then extra memory consumption will be just in O(log(N)).
so that the paths are compared (essentailly similar to accepted answer - but the paths is calculated by assuming pointer node is not present in the binary tree node)
Just for the completion (not related to question), LCA in BST (O(log(N))
Tests
Recursive:
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;
}
where above private recursive version is invoked by following public method:
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;
}
Solution by keeping track of paths of both nodes:
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;
}
where FindNodeAndPath is defined as
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) - not related (just for completion for reference)
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;
}
Unit Tests
[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);
}
}
如果这里有人感兴趣的伪代码（University主页作品）就是其中之一。
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语言编程这个问题。 虽然代码显示了二叉搜索树（只要插入（）而言），但该算法适用于二叉树为好。 我们的想法是走了过来，从节点谎言到节点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);
}
可以有一个更加办法。 但是作为一个在答案已经建议是效率不高。
创建节点N1的路径矢量。
创建节点n2的第二路径向量。
这意味着从一个节点集路径矢量将穿过到达有问题的节点。
比较这两个路径矢量。 他们不匹配指数，即指数在返回节点 - 1，这将使LCA。
这种方法缺点：
需要两次遍历树计算路径载体。 需要addtional O（1H）空间来存储路径矢量。
然而，这很容易实现和理解为好。
代码计算路径矢量：
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;
}
粗暴的方式：
上述的方法的问题是，我们会做的“查找”多次，也就是说，每一个节点获得经过多次的可能性。 我们可以克服这个问题，如果我们可以记录信息，从而不会再处理它（想想动态规划）。
因此，而不是做的找到每一个节点上，我们不断的为已发现的最新的记录。
更好的方法：
码：
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;
}
}
代码广度优先搜索，以确保两个节点都在树中。 只有再向前与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;
}
}
你是正确的，没有父节点，穿越解决方案会给你O（n）的时间复杂度。
遍历方法假设你发现LCA节点A和B，最直接的方法是首先从根路径A，然后得到根路径B.一旦你有这两条路径，你可以很容易地在它们之间迭代并找到最后的共同节点，这是A和B的最低共同祖先
递归解决方案的另一个方法是使用递归。 首先，我们可以从两个左树和右树得到LCA（如果存在）。 如果任一的A或B是根节点，则根是LCA，我们只是返回根，这是递归的终点。 正如我们保持划分成树子树，最终，我们会打要么A和B.
要结合子解决问题的方法，如果LCA（左树）返回一个节点，我们知道，A和B都定位左树和返回的节点是最后的结果。 如果两个LCA（左）和LCA（右）返回非空节点，这意味着A和B分别是在左边和右边的树。 在这种情况下，根节点是最低的公共节点。
检查最近公共祖先进行详细的分析和解决方案。
一些解决方案，这里假设有参考根节点，一些假设树是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：递归-更快
- 时间复杂度：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：迭代-使用父指针-慢
- 时间复杂度：O（N） - 在最坏的情况下，我们可能会访问二叉树的所有节点。
- 空间复杂度：O（N） - 利用父指针散列的表，ancestor_set和队列空间，将是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;
}
}
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://i.stack.imgur.com/Sz5KZ.gif', '推荐 太酷不给撩 的文章《如何找到在任何二叉树两个节点的最低共同祖先？(How to find the lowest comm》','https://www.manongdao.com/article-1149523.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}