The nearest common ancestor of binary tree

Topic link ： The nearest common ancestor of a binary tree

Title Description

Given a binary tree , Find the nearest common ancestor of the two specified nodes in the tree .

In Baidu Encyclopedia, the most recent definition of public ancestor is ：“ For a tree T Two nodes of p、q, The nearest common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible （ A node can also be its own ancestor ）.”

Topic analysis

For a binary tree , There are many ways to find the nearest common ancestor node , Only one of them is introduced here . According to the meaning , To find the nearest public ancestor node , First, for a node , If p and q In the left and right subtrees of this node , So the node is pq The nearest common ancestor node of . If both nodes are in the left or right subtree of a node , Then you can recursively go to the next node for judgment , Note that a node may be its own ancestor node , namely p Nodes may also be q The ancestor node of the node , Situation judgment is required . The code implementation is as follows ：

Code implementation

bool Find(TreeNode* root, TreeNode* key)// lookup key Whether it exists in the subtree of this node 
{
    
	if (root == nullptr)
	{
    
		return false;
	}
	if (root == key)
	{
    
		return true;
	}
	return Find(root->left, key) || Find(root->right, key);
}


TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
{
    
	bool leftp = Find(root->left, p);
	bool rightp = Find(root->right, p);
	bool leftq = Find(root->left, q);
	bool rightq = Find(root->right, q);
	if (root == p || root == q)
	{
    
		return root;
	}
	else if ((leftp && rightq)||(rightp && leftq))//p and q Respectively in root On the left and right subtrees of 
	{
    
		return root;
	}
	else if ((leftp && leftq))//p and q On the same left 
	{
    
		return lowestCommonAncestor(root->left, p, q);
	}
	else if (rightp && rightq)
	{
    
		return lowestCommonAncestor(root->right, p, q);
	}
	else
	{
    
		return nullptr;
	}

}