这里的二叉树不一定是二叉搜索树。
该结构可以被视为 -
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)，因为它们只不过是数组中的简单迭代）。但很有可能这是错误的。:-)
但这是一种非常粗糙的方法，我不确定它是否会在某些情况下失效。这个问题还有其他（可能更优化）的解决方案吗？
从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;
}
}
}
尼克约翰逊是正确的，如果你没有父指针，那么 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) [线性] 时间准备的算法，然后找到任何pair 只需要 O(1) [常数] 时间。有关这些算法的参考，请参阅Wikipedia上最低的共同祖先问题页面。（感谢 Jason 最初发布此链接）
这是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是根，depth(v) = 0；否则，depth(v) = depth(parent(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 的离线最小共同祖先算法已经足够好了（参见Wikipedia）。维基百科上有更多关于这个问题（最低共同祖先问题）的内容。
要找出两个节点的共同祖先：-
这适用于二叉搜索树。
我尝试使用 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，必须找到祖先，都在同一个子树中（意味着它们的值都小于或都大于根的值），就从整个树向下走。
这直接从根走到 Least Common Ancestor ，而不是看树的其余部分，所以它几乎和它一样快。有几种方法可以做到。
迭代，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
爪哇
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
爪哇
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 的最小共同祖先
在后序中，我们在 8 和 11 之后有 =>9,14,15,13,12,7 在前序中，我们在 8 和 11 之前有 =>7,3,1,0,2,6,4,5,12,9
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(log(32))
- x & y 的二进制符号的共同前缀是共同祖先
- 由较大的位数表示的那个被 k >> diff 带到相同的位
- k = x^y 删除 x & y 的公共前缀
- 查找表示剩余后缀的位
- 将 x 或 y 移动后缀位以获得共同的前缀，即共同的祖先。
这是有效的，因为基本上递归地将较大的数字除以二，直到两个数字相等。这个数字就是共同的祖先。除法实际上是右移操作。所以我们需要找到两个数字的共同前缀来找到最近的祖先
两个节点之间的最低共同祖先，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)
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;
}
这是 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)
...
找到最低共同祖先的最简单方法是使用以下算法：
检查根节点
如果 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;
}
我找到了解决方案
根据 3 次遍历，您可以决定谁是 LCA。从 LCA 找到两个节点的距离。将这两个距离相加，就是答案。
以下是我的想法，
复杂性：第 1 步：O(n)，第 2 步 =~ O(n)，总计 =~ O(n)。
以下是 c# (.net) 中的两种方法（都在上面讨论过）供参考：
在二叉树中查找 LCA 的递归版本（O(N) - 最多访问每个节点）（解决方案的要点是 LCA 是（a）二叉树中唯一的节点，其中两个元素都位于子树的任一侧（左和正确的）是 LCA。（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);
}
}
如果有人对伪代码（大学家庭工作）感兴趣，这里就是其中之一。
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 编程语言解决这个问题的方法。尽管代码显示了二叉搜索树（就 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);
}
可以有另外一种方法。但是，它不像答案中已经建议的那样有效。
为节点 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;
}
粗暴方式：
上述方法的问题是我们将多次“查找”，即每个节点都有可能被多次遍历。如果我们可以记录信息以便不再处理它（想想动态编程），我们就可以克服这个问题。
因此，我们不是查找每个节点，而是记录已经找到的内容。
更好的方法：
代码：
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;
}
}
这里的一些解决方案假设存在对根节点的引用，一些假设树是 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
}
解决方案 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) - 使用父指针哈希表、祖先集和队列的空间，每个都是 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)。如果
如果一个节点的左右值都不为空，那么该节点就是您的答案（从顶部开始的第三个“如果”）。在找到一个值时进行迭代，因为所有值都是唯一的并且必须存在，我们不需要搜索它的后代。所以只需返回找到的匹配节点。如果一个节点的左右分支内容 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);
}
}
PHP 中的代码。我假设这棵树是一个数组二叉树。因此，您甚至不需要树来计算 LCA。输入：两个节点的索引输出：LCA的索引
<?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));
?>
请告诉我是否有任何不足之处。
//如果两个值都小于当前节点则遍历左子树 //或者如果两个值都大于当前节点则遍历右子树 //或者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;
}
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.
}
}