- 首页 > it技术 > >
★ACM基础知识|求解二叉树中两个节点的最近公共祖先（LCA）
/************************************************************************/
/*
非递归的方法下面是一个简单的复杂度为 O(n) 的算法，解决LCA问题1) 找到从根到n1的路径，并存储在一个向量或数组中。
2)找到从根到n2的路径，并存储在一个向量或数组中。
3) 遍历这两条路径，直到遇到一个不同的节点，则前面的那个即为最低公共祖先.*/
/************************************************************************///二叉树节点
struct Node
{
int key;
Node *left, *right;
};
//找到从root到 节点值为key的路径,存储在path中。没有的话返回-1
bool findpath(Node * root,vector &path,int key)
{
if(root == NULL) return false;
path.push_back(root->key);
if(root->key == key) return true;
//左子树或右子树 是否找到,找到的话当前节点就在路径中了
bool find =( findpath(root->left, path, key) || findpath(root->right,path ,key) );
if(find) return true;
//该节点下未找到就弹出
path.pop_back();
return false;
}int findLCA(Node * root,int key1,int key2)
{
vector path1,path2;
bool find1 = findpath(root, path1, key1);
bool find2 = findpath(root, path2, key2);
if(find1 && find2)
{
int ans ;
for(int i=0;
i < path1.size();
i++)
{
if(path1[i] != path2[i])
{
break;
}
else
{
ans = path1[i];
}
}
return ans;
}
return -1;
}/************************************************************************/
/*
递归求解方法从root开始遍历，如果n1和n2中的任一个和root匹配，那么root就是LCA。
如果都不匹配，则分别递归左、右子树，
如果有一个 key（n1或n2）出现在左子树，并且另一个key(n1或n2)出现在右子树，则root就是LCA.
如果两个key都出现在左子树，则说明LCA在左子树中，否则在右子树。
*/
/************************************************************************/struct Node
{
struct Node *left, *right;
int key;
};
// 返回n1和n2的 LCA的指针
// 假设n1和n2都出现在树中
struct Node *findLCA(struct Node* root, int n1, int n2)
{
if (root == NULL) return NULL;
// 只要n1 或 n2 的任一个匹配即可
//(注意：如果 一个节点是另一个祖先，则返回的是祖先节点。因为递归是要返回到祖先的 )
if (root->key == n1 || root->key == n2)
return root;
// 分别在左右子树查找
Node *left_lca= findLCA(root->left, n1, n2);
Node *right_lca = findLCA(root->right, n1, n2);
// 如果都返回非空指针 Non-NULL, 则说明两个节点分别出现了在两个子树中，则当前节点肯定为LCA
if (left_lca && right_lca)return root;
// 如果一个为空，在说明LCA在另一个子树
return (left_lca != NULL)? left_lca: right_lca;
}
推荐阅读
