给定二元搜索树中两个值n1和n2的值，找到 L 欧维斯特 C 奥蒙 A. ncestor（LCA）。您可以假设这两个值都存在于树中。
null
例如：
Tree:
![图片[1]-二叉搜索树中最低的共同祖先。-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/cdn-uploads/2009/08/BST_LCA.gif)
Input: LCA of 10 and 14Output: 12Explanation: 12 is the closest node to both 10 and 14 which is a ancestor of both the nodes.Input: LCA of 8 and 14Output: 8Explanation: 8 is the closest node to both 8 and 14 which is a ancestor of both the nodes.Input: LCA of 10 and 22Output: 20Explanation: 20 is the closest node to both 10 and 22 which is a ancestor of both the nodes.
以下是 生命周期评价的定义 维基百科 :
让我们做一棵有根的树吧。两个节点n1和n2之间的最低共同祖先被定义为T中的最低节点，其n1和n2都是子节点（我们允许一个节点是其自身的子节点）。 T中n1和n2的LCA是距离根部最远的n1和n2的共同祖先。例如，作为确定树中成对节点之间距离的过程的一部分，计算最低共同祖先可能很有用：从n1到n2的距离可以计算为从根到n1的距离，加上从根到n2的距离，减去从根到最低共同祖先的距离的两倍。（来源） 维基 )
方法： 对于二元搜索树，当从上到下遍历树时，位于两个数字n1和n2之间的第一个节点是节点的LCA，即位于n1和n2（n1<=n<=n2）之间的具有最低深度的第一个节点n。所以递归地遍历BST in，如果节点的值大于n1和n2，那么我们的LCA位于节点的左侧，如果它小于n1和n2，那么LCA位于右侧。否则，根为LCA（假设BST中同时存在n1和n2）。
算法：
- 创建一个递归函数，该函数接受一个节点和两个值n1和n2。
- 如果当前节点的值小于n1和n2，则LCA位于右侧子树中。调用右子树的递归函数。
- 如果当前节点的值大于n1和n2，则LCA位于左子树中。调用左子树的递归函数。
- 如果上述两种情况都为假，则将当前节点作为LCA返回。
实施：
C++
// A recursive CPP program to find // LCA of two nodes n1 and n2. #include <bits/stdc++.h> using namespace std; class node { public : int data; node* left, *right; }; /* Function to find LCA of n1 and n2. The function assumes that both n1 and n2 are present in BST */ node *lca(node* root, int n1, int n2) { if (root == NULL) return NULL; // If both n1 and n2 are smaller // than root, then LCA lies in left if (root->data > n1 && root->data > n2) return lca(root->left, n1, n2); // If both n1 and n2 are greater than // root, then LCA lies in right if (root->data < n1 && root->data < n2) return lca(root->right, n1, n2); return root; } /* Helper function that allocates a new node with the given data.*/ node* newNode( int data) { node* Node = new node(); Node->data = data; Node->left = Node->right = NULL; return (Node); } /* Driver code*/ int main() { // Let us construct the BST // shown in the above figure node *root = newNode(20); root->left = newNode(8); root->right = newNode(22); root->left->left = newNode(4); root->left->right = newNode(12); root->left->right->left = newNode(10); root->left->right->right = newNode(14); int n1 = 10, n2 = 14; node *t = lca(root, n1, n2); cout << "LCA of " << n1 << " and " << n2 << " is " << t->data<<endl; n1 = 14, n2 = 8; t = lca(root, n1, n2); cout<< "LCA of " << n1 << " and " << n2 << " is " << t->data << endl; n1 = 10, n2 = 22; t = lca(root, n1, n2); cout << "LCA of " << n1 << " and " << n2 << " is " << t->data << endl; return 0; } // This code is contributed by rathbhupendra |
C
// A recursive C program to find LCA of two nodes n1 and n2. #include <stdio.h> #include <stdlib.h> struct node { int data; struct node* left, *right; }; /* Function to find LCA of n1 and n2. The function assumes that both n1 and n2 are present in BST */ struct node *lca( struct node* root, int n1, int n2) { if (root == NULL) return NULL; // If both n1 and n2 are smaller than root, then LCA lies in left if (root->data > n1 && root->data > n2) return lca(root->left, n1, n2); // If both n1 and n2 are greater than root, then LCA lies in right if (root->data < n1 && root->data < n2) return lca(root->right, n1, n2); return root; } /* Helper function that allocates a new node with the given data.*/ struct node* newNode( int data) { struct node* node = ( struct node*) malloc ( sizeof ( struct node)); node->data = data; node->left = node->right = NULL; return (node); } /* Driver program to test lca() */ int main() { // Let us construct the BST shown in the above figure struct node *root = newNode(20); root->left = newNode(8); root->right = newNode(22); root->left->left = newNode(4); root->left->right = newNode(12); root->left->right->left = newNode(10); root->left->right->right = newNode(14); int n1 = 10, n2 = 14; struct node *t = lca(root, n1, n2); printf ( "LCA of %d and %d is %d " , n1, n2, t->data); n1 = 14, n2 = 8; t = lca(root, n1, n2); printf ( "LCA of %d and %d is %d " , n1, n2, t->data); n1 = 10, n2 = 22; t = lca(root, n1, n2); printf ( "LCA of %d and %d is %d " , n1, n2, t->data); getchar (); return 0; } |
JAVA
// Recursive Java program to print lca of two nodes // A binary tree node class Node { int data; Node left, right; Node( int item) { data = item; left = right = null ; } } class BinaryTree { Node root; /* Function to find LCA of n1 and n2. The function assumes that both n1 and n2 are present in BST */ Node lca(Node node, int n1, int n2) { if (node == null ) return null ; // If both n1 and n2 are smaller than root, then LCA lies in left if (node.data > n1 && node.data > n2) return lca(node.left, n1, n2); // If both n1 and n2 are greater than root, then LCA lies in right if (node.data < n1 && node.data < n2) return lca(node.right, n1, n2); return node; } /* Driver program to test lca() */ public static void main(String args[]) { // Let us construct the BST shown in the above figure BinaryTree tree = new BinaryTree(); tree.root = new Node( 20 ); tree.root.left = new Node( 8 ); tree.root.right = new Node( 22 ); tree.root.left.left = new Node( 4 ); tree.root.left.right = new Node( 12 ); tree.root.left.right.left = new Node( 10 ); tree.root.left.right.right = new Node( 14 ); int n1 = 10 , n2 = 14 ; Node t = tree.lca(tree.root, n1, n2); System.out.println( "LCA of " + n1 + " and " + n2 + " is " + t.data); n1 = 14 ; n2 = 8 ; t = tree.lca(tree.root, n1, n2); System.out.println( "LCA of " + n1 + " and " + n2 + " is " + t.data); n1 = 10 ; n2 = 22 ; t = tree.lca(tree.root, n1, n2); System.out.println( "LCA of " + n1 + " and " + n2 + " is " + t.data); } } // This code has been contributed by Mayank Jaiswal |
蟒蛇3
# A recursive python program to find LCA of two nodes # n1 and n2 # A Binary tree node class Node: # Constructor to create a new node def __init__( self , data): self .data = data self .left = None self .right = None # Function to find LCA of n1 and n2. The function assumes # that both n1 and n2 are present in BST def lca(root, n1, n2): # Base Case if root is None : return None # If both n1 and n2 are smaller than root, then LCA # lies in left if (root.data > n1 and root.data > n2): return lca(root.left, n1, n2) # If both n1 and n2 are greater than root, then LCA # lies in right if (root.data < n1 and root.data < n2): return lca(root.right, n1, n2) return root # Driver program to test above function # Let us construct the BST shown in the figure root = Node( 20 ) root.left = Node( 8 ) root.right = Node( 22 ) root.left.left = Node( 4 ) root.left.right = Node( 12 ) root.left.right.left = Node( 10 ) root.left.right.right = Node( 14 ) n1 = 10 ; n2 = 14 t = lca(root, n1, n2) print ( "LCA of %d and %d is %d" % (n1, n2, t.data)) n1 = 14 ; n2 = 8 t = lca(root, n1, n2) print ( "LCA of %d and %d is %d" % (n1, n2 , t.data)) n1 = 10 ; n2 = 22 t = lca(root, n1, n2) print ( "LCA of %d and %d is %d" % (n1, n2, t.data)) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
using System; // Recursive C# program to print lca of two nodes // A binary tree node public class Node { public int data; public Node left, right; public Node( int item) { data = item; left = right = null ; } } public class BinaryTree { public Node root; /* Function to find LCA of n1 and n2. The function assumes that both n1 and n2 are present in BST */ public virtual Node lca(Node node, int n1, int n2) { if (node == null ) { return null ; } // If both n1 and n2 are smaller than root, then LCA lies in left if (node.data > n1 && node.data > n2) { return lca(node.left, n1, n2); } // If both n1 and n2 are greater than root, then LCA lies in right if (node.data < n1 && node.data < n2) { return lca(node.right, n1, n2); } return node; } /* Driver program to test lca() */ public static void Main( string [] args) { // Let us construct the BST shown in the above figure BinaryTree tree = new BinaryTree(); tree.root = new Node(20); tree.root.left = new Node(8); tree.root.right = new Node(22); tree.root.left.left = new Node(4); tree.root.left.right = new Node(12); tree.root.left.right.left = new Node(10); tree.root.left.right.right = new Node(14); int n1 = 10, n2 = 14; Node t = tree.lca(tree.root, n1, n2); Console.WriteLine( "LCA of " + n1 + " and " + n2 + " is " + t.data); n1 = 14; n2 = 8; t = tree.lca(tree.root, n1, n2); Console.WriteLine( "LCA of " + n1 + " and " + n2 + " is " + t.data); n1 = 10; n2 = 22; t = tree.lca(tree.root, n1, n2); Console.WriteLine( "LCA of " + n1 + " and " + n2 + " is " + t.data); } } // This code is contributed by Shrikant13 |
Javascript
<script> // Recursive JavaScript program to print lca of two nodes // A binary tree node class Node { constructor(item) { this .data=item; this .left= this .right= null ; } } let root; function lca(node,n1,n2) { if (node == null ) return null ; // If both n1 and n2 are smaller than root, // then LCA lies in left if (node.data > n1 && node.data > n2) return lca(node.left, n1, n2); // If both n1 and n2 are greater than root, // then LCA lies in right if (node.data < n1 && node.data < n2) return lca(node.right, n1, n2); return node; } /* Driver program to test lca() */ // Let us construct the BST shown in the above figure root = new Node(20); root.left = new Node(8); root.right = new Node(22); root.left.left = new Node(4); root.left.right = new Node(12); root.left.right.left = new Node(10); root.left.right.right = new Node(14); let n1 = 10, n2 = 14; let t = lca(root, n1, n2); document.write( "LCA of " + n1 + " and " + n2 + " is " + t.data+ "<br>" ); n1 = 14; n2 = 8; t = lca(root, n1, n2); document.write( "LCA of " + n1 + " and " + n2 + " is " + t.data+ "<br>" ); n1 = 10; n2 = 22; t = lca(root, n1, n2); document.write( "LCA of " + n1 + " and " + n2 + " is " + t.data+ "<br>" ); // This code is contributed by avanitrachhadiya2155 </script> |
输出
LCA of 10 and 14 is 12 LCA of 14 and 8 is 8 LCA of 10 and 22 is 20
复杂性分析：
- 时间复杂性： O（h）。 上述解的时间复杂度为O（h），其中h是树的高度。
- 空间复杂性： O（h）。 如果忽略递归堆栈空间，则上述解决方案的空间复杂度是恒定的。
迭代实现： 上述解决方案使用递归。递归解决方案需要函数调用堆栈形式的额外空间。因此，可以实现一个迭代解决方案，它不会以函数调用堆栈的形式占用空间。
实施：
C++
// A recursive CPP program to find // LCA of two nodes n1 and n2. #include <bits/stdc++.h> using namespace std; class node { public : int data; node* left, *right; }; /* Function to find LCA of n1 and n2. The function assumes that both n1 and n2 are present in BST */ node *lca(node* root, int n1, int n2) { while (root != NULL) { // If both n1 and n2 are smaller than root, // then LCA lies in left if (root->data > n1 && root->data > n2) root = root->left; // If both n1 and n2 are greater than root, // then LCA lies in right else if (root->data < n1 && root->data < n2) root = root->right; else break ; } return root; } /* Helper function that allocates a new node with the given data.*/ node* newNode( int data) { node* Node = new node(); Node->data = data; Node->left = Node->right = NULL; return (Node); } /* Driver code*/ int main() { // Let us construct the BST // shown in the above figure node *root = newNode(20); root->left = newNode(8); root->right = newNode(22); root->left->left = newNode(4); root->left->right = newNode(12); root->left->right->left = newNode(10); root->left->right->right = newNode(14); int n1 = 10, n2 = 14; node *t = lca(root, n1, n2); cout << "LCA of " << n1 << " and " << n2 << " is " << t->data<<endl; n1 = 14, n2 = 8; t = lca(root, n1, n2); cout<< "LCA of " << n1 << " and " << n2 << " is " << t->data << endl; n1 = 10, n2 = 22; t = lca(root, n1, n2); cout << "LCA of " << n1 << " and " << n2 << " is " << t->data << endl; return 0; } // This code is contributed by rathbhupendra |
C
// A recursive C program to find LCA of two nodes n1 and n2. #include <stdio.h> #include <stdlib.h> struct node { int data; struct node* left, *right; }; /* Function to find LCA of n1 and n2. The function assumes that both n1 and n2 are present in BST */ struct node *lca( struct node* root, int n1, int n2) { while (root != NULL) { // If both n1 and n2 are smaller than root, then LCA lies in left if (root->data > n1 && root->data > n2) root = root->left; // If both n1 and n2 are greater than root, then LCA lies in right else if (root->data < n1 && root->data < n2) root = root->right; else break ; } return root; } /* Helper function that allocates a new node with the given data.*/ struct node* newNode( int data) { struct node* node = ( struct node*) malloc ( sizeof ( struct node)); node->data = data; node->left = node->right = NULL; return (node); } /* Driver program to test lca() */ int main() { // Let us construct the BST shown in the above figure struct node *root = newNode(20); root->left = newNode(8); root->right = newNode(22); root->left->left = newNode(4); root->left->right = newNode(12); root->left->right->left = newNode(10); root->left->right->right = newNode(14); int n1 = 10, n2 = 14; struct node *t = lca(root, n1, n2); printf ( "LCA of %d and %d is %d " , n1, n2, t->data); n1 = 14, n2 = 8; t = lca(root, n1, n2); printf ( "LCA of %d and %d is %d " , n1, n2, t->data); n1 = 10, n2 = 22; t = lca(root, n1, n2); printf ( "LCA of %d and %d is %d " , n1, n2, t->data); getchar (); return 0; } |
JAVA
// Recursive Java program to print lca of two nodes // A binary tree node class Node { int data; Node left, right; Node( int item) { data = item; left = right = null ; } } class BinaryTree { Node root; /* Function to find LCA of n1 and n2. The function assumes that both n1 and n2 are present in BST */ static Node lca(Node root, int n1, int n2) { while (root != null ) { // If both n1 and n2 are smaller // than root, then LCA lies in left if (root.data > n1 && root.data > n2) root = root.left; // If both n1 and n2 are greater // than root, then LCA lies in right else if (root.data < n1 && root.data < n2) root = root.right; else break ; } return root; } /* Driver program to test lca() */ public static void main(String args[]) { // Let us construct the BST shown in the above figure BinaryTree tree = new BinaryTree(); tree.root = new Node( 20 ); tree.root.left = new Node( 8 ); tree.root.right = new Node( 22 ); tree.root.left.left = new Node( 4 ); tree.root.left.right = new Node( 12 ); tree.root.left.right.left = new Node( 10 ); tree.root.left.right.right = new Node( 14 ); int n1 = 10 , n2 = 14 ; Node t = tree.lca(tree.root, n1, n2); System.out.println( "LCA of " + n1 + " and " + n2 + " is " + t.data); n1 = 14 ; n2 = 8 ; t = tree.lca(tree.root, n1, n2); System.out.println( "LCA of " + n1 + " and " + n2 + " is " + t.data); n1 = 10 ; n2 = 22 ; t = tree.lca(tree.root, n1, n2); System.out.println( "LCA of " + n1 + " and " + n2 + " is " + t.data); } } // This code is contributed by SHUBHAMSINGH10 |
蟒蛇3
# A recursive python program to find LCA of two nodes # n1 and n2 # A Binary tree node class Node: # Constructor to create a new node def __init__( self , data): self .data = data self .left = None self .right = None # Function to find LCA of n1 and n2. # The function assumes that both # n1 and n2 are present in BST def lca(root, n1, n2): while root: # If both n1 and n2 are smaller than root, # then LCA lies in left if root.data > n1 and root.data > n2: root = root.left # If both n1 and n2 are greater than root, # then LCA lies in right elif root.data < n1 and root.data < n2: root = root.right else : break return root # Driver program to test above function # Let us construct the BST shown in the figure root = Node( 20 ) root.left = Node( 8 ) root.right = Node( 22 ) root.left.left = Node( 4 ) root.left.right = Node( 12 ) root.left.right.left = Node( 10 ) root.left.right.right = Node( 14 ) n1 = 10 ; n2 = 14 t = lca(root, n1, n2) print ( "LCA of %d and %d is %d" % (n1, n2, t.data)) n1 = 14 ; n2 = 8 t = lca(root, n1, n2) print ( "LCA of %d and %d is %d" % (n1, n2 , t.data)) n1 = 10 ; n2 = 22 t = lca(root, n1, n2) print ( "LCA of %d and %d is %d" % (n1, n2, t.data)) # This Code is Contributed by Sumit Bhardwaj (Timus) |
C#
using System; // Recursive C# program to print lca of two nodes // A binary tree node public class Node { public int data; public Node left, right; public Node( int item) { data = item; left = right = null ; } } public class BinaryTree { public Node root; /* Function to find LCA of n1 and n2. The function assumes that both n1 and n2 are present in BST */ public virtual Node lca(Node root, int n1, int n2) { while (root != null ) { // If both n1 and n2 are smaller than // root, then LCA lies in left if (root.data > n1 && root.data > n2) root = root.left; // If both n1 and n2 are greater than // root, then LCA lies in right else if (root.data < n1 && root.data < n2) root = root.right; else break ; } return root; } /* Driver program to test lca() */ public static void Main( string [] args) { // Let us construct the BST shown in the above figure BinaryTree tree = new BinaryTree(); tree.root = new Node(20); tree.root.left = new Node(8); tree.root.right = new Node(22); tree.root.left.left = new Node(4); tree.root.left.right = new Node(12); tree.root.left.right.left = new Node(10); tree.root.left.right.right = new Node(14); int n1 = 10, n2 = 14; Node t = tree.lca(tree.root, n1, n2); Console.WriteLine( "LCA of " + n1 + " and " + n2 + " is " + t.data); n1 = 14; n2 = 8; t = tree.lca(tree.root, n1, n2); Console.WriteLine( "LCA of " + n1 + " and " + n2 + " is " + t.data); n1 = 10; n2 = 22; t = tree.lca(tree.root, n1, n2); Console.WriteLine( "LCA of " + n1 + " and " + n2 + " is " + t.data); } } // This code is contributed by Shrikant13 |
Javascript
<script> // Recursive Javascript program to // print lca of two nodes // A binary tree node class Node { constructor(item) { this .data = item; this .left = null ; this .right = null ; } } var root = null ; /* Function to find LCA of n1 and n2. The function assumes that both n1 and n2 are present in BST */ function lca(root, n1, n2) { while (root != null ) { // If both n1 and n2 are smaller than // root, then LCA lies in left if (root.data > n1 && root.data > n2) root = root.left; // If both n1 and n2 are greater than // root, then LCA lies in right else if (root.data < n1 && root.data < n2) root = root.right; else break ; } return root; } // Driver code // Let us construct the BST shown // in the above figure root = new Node(20); root.left = new Node(8); root.right = new Node(22); root.left.left = new Node(4); root.left.right = new Node(12); root.left.right.left = new Node(10); root.left.right.right = new Node(14); var n1 = 10, n2 = 14; var t = lca(root, n1, n2); document.write( "LCA of " + n1 + " and " + n2 + " is " + t.data + "<br>" ); n1 = 14; n2 = 8; t = lca(root, n1, n2); document.write( "LCA of " + n1 + " and " + n2 + " is " + t.data+ "<br>" ); n1 = 10; n2 = 22; t = lca(root, n1, n2); document.write( "LCA of " + n1 + " and " + n2 + " is " + t.data+ "<br>" ); // This code is contributed by rrrtnx </script> |
输出
LCA of 10 and 14 is 12 LCA of 14 and 8 is 8 LCA of 10 and 22 is 20
复杂性分析：
- 时间复杂性： O（h）。 上述解的时间复杂度为O（h），其中h是树的高度。
- 空间复杂性： O（1）。 上述解的空间复杂度是恒定的。
https://www.youtube.com/watch?v=zlTsz
-apm4U
您可能还想看到以下文章：
运动 上述函数假设n1和n2都在BST中。如果n1和n2不存在，则它们可能返回错误的结果。如果BST中不存在n1或n2或两者，则扩展上述解决方案以返回NULL。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
