学步园

【算法面试题】寻找二叉搜索树中两个节点的最近公共祖先节点

http://geeksforgeeks.org/?p=1029

给定了一个二叉搜索树中任意的两个节点的值，要你写一个c/c++程序，去找到这两个节点的最近公共祖先，你可以假定给定的值存在于二叉树的某个节点中。

函数声明：

int FindLowestCommonAncestor(node* root, int value1, int value)

 输入: 4 和 14
 输出: 8
 （4和14的共同祖先有{8, 20}，其中8是最近的公共祖先节点）

算法：

基本思想是：给定二叉树中的两个节点n1, n2(假定n1<n2), 其最近的公共祖先节点的值n应该满足 n1<n<n2，所以我们可以前序遍历二叉搜索树，当发现一个节点的值在n1和n2之间时，则此节点为所求节点。如果节点的值大于n1和n2，则所求节点在当前节点的左子树；否则在右子树。

#include <stdio.h><br /> #include <stdlib.h> </p> <p>/* A binary tree node has data, pointer to left child<br /> and a pointer to right child */ </p> <p>struct node<br /> {<br /> int data;<br /> struct node* left;<br /> struct node* right;<br /> }; </p> <p>struct node* newNode(int ); </p> <p>/* Function to find least comman ancestor of n1 and n2 */<br /> int leastCommanAncestor(struct node* root, int n1, int n2)<br /> {<br /> /* If we have reached a leaf node then LCA doesn't exist<br /> If root->data is equal to any of the inputs then input is<br /> not valid. For example 20, 22 in the given figure */ </p> <p> if(root == NULL || root->data == n1 || root->data == n2)<br /> return -1; </p> <p> /* If any of the input nodes is child of the current node<br /> we have reached the LCA. For example, in the above figure<br /> if we want to calculate LCA of 12 and 14, recursion should<br /> terminate when we reach 8*/<br /> if((root->right != NULL) &&<br /> (root->right->data == n1 || root->right->data == n2))<br /> return root->data; </p> <p> if((root->left != NULL) &&<br /> (root->left->data == n1 || root->left->data == n2))<br /> return root->data; </p> <p> if(root->data > n1 && root->data < n2)<br /> return root->data; </p> <p> if(root->data > n1 && root->data > n2)<br /> return leastCommanAncestor(root->left, n1, n2); </p> <p> if(root->data < n1 && root->data < n2)<br /> return leastCommanAncestor(root->right, n1, n2);<br /> } </p> <p>/* Helper function that allocates a new node with the<br /> given data and NULL left and right pointers. */<br /> struct node* newNode(int data)<br /> {<br /> struct node* node = (struct node*)<br /> malloc(sizeof(struct node));<br /> node->data = data;<br /> node->left = NULL;<br /> node->right = NULL;<br /> return(node);<br /> } </p> <p>/* Driver program to test mirror() */<br /> int main()<br /> {<br /> struct node *root = newNode(2);<br /> root->left = newNode(1);<br /> root->ight = newNode(4);<br /> root->right->left = newNode(3);<br /> root->right->right = newNode(5); </p> <p>/* Constructed binary search tree is<br /> 2<br /> / /<br /> 1 4<br /> / /<br /> 3 5<br /> */ </p> <p> printf("/n The Least Common Ancestor is /n");<br /> printf("%d", leastCommanAncestor(root, 3, 5)); </p> <p> getchar();<br /> return 0;<br /> }<br />