最近公共祖先

发表于   |   分类于   |  

Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

如果这个二叉树是一个二叉排序树

我们可以判断几种情况

（1）两个节点都在树的左子树
（2）两个节点都在树的右子树
（3）一个节点在左子树，一个节点在右子树（root为LCA）
（4）一个节点为root（root为LCA）

1
2
3
4
5
6
7
8
9
Node*LCA(Node*root,Node*p,Node*q)
{
	if(root==NULL||p==NULL||q==NULL) return NULL;
	if(root==p||root==q) return root;
	if(root->val>p->val&&root->val<q->val) return root;
	if(root->val>q->val&&root->val<p->val) return root;
	if(root->val>p->val&&root->val>q->val) return LCA(root->left,p,q);
	else return LCA(root->right,p,q);
}

如果不是二叉排序树呢？

方法一
计算左右子树上是否有p或者q，如果有一个返回1，如果有2个返回2，如果没有，返回0
（1）如果左子树返回了1，则右子树也有一个，root为LCA。
（2）如果左子树返回了2，则右子树没有，继续LCA(root->left,p,q);
（3）如果左子树返回了0，则继续LCA(root->right,p,q);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int countMatchesPQ(TreeNode *root, TreeNode *p, TreeNode *q) {
  if (!root) return 0;
  int matches = countMatchesPQ(root->left, p, q) + countMatchesPQ(root->right, p, q);
  if (root == p || root == q)
    return 1 + matches;
  else
    return matches;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || !p || !q) return NULL;
  if (root == p || root == q) return root;
  int totalMatches = countMatchesPQ(root->left, p, q);
  if (totalMatches == 1)
    return root;
  else if (totalMatches == 2)
    return lowestCommonAncestor(root->left, p, q);
  else /* totalMatches == 0 */
    return lowestCommonAncestor(root->right, p, q);
    }

方法二
其实和前面的都是一个思路，看L,R哪个为空，为空的表明那个分支没有p,或者q
当L,R不空时，分支会把L或者R不断的传送到上一个迭代

1
2
3
4
5
6
7
8
9
 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       if (!root || !p || !q) return NULL;
 if (root == p || root == q) return root;
 TreeNode* L=lowestCommonAncestor(root->left,p,q);
 TreeNode* R=lowestCommonAncestor(root->right,p,q);
 if(L&&R) return root;
 else if(L) return L;
 else return R;
}