/*方法一：借助容器
step:   1)先设置所有结点的父节点，而head的父结点置成自己本身
        2)再从no1往上串，将其祖先们放到一个容器里面
        3)no2不断往上串，什么时候no2的祖先出现在no1的祖先里面就返回这个共同祖先
*/

#include<unordered_map>
#include<unordered_set>
Node* lca(Node* head, Node* no1, Node* no2) {
	unordered_map<Node*, Node*> father;
	father.insert(make_pair(head, head));//根结点的父亲设成自己
	process(head, father);
	Node* cur = no1;
	unordered_set<Node*> no1Ancestor;
	while (cur != father[cur]) {//自由根结点父亲等于自己，所以将head装进去就结束
		no1Ancestor.insert(cur);
		cur = father[cur];//往上串
	}
	cur = no2;
	while (cur != father[cur]) {
		if (no1Ancestor.find(cur) != no1Ancestor.end())//判断是否no2的祖先出现在no1的祖先里面
			return *(no1Ancestor.find(cur));
		cur = father[cur];
	}
}
//设置父结点函数
void process(Node* head, unordered_map<Node*, Node*>& father) {
	if (head == NULL)
		return;
	father.insert(make_pair(head->left, head));//左右子结点的父亲都是头
	father.insert(make_pair(head->right, head));
	process(head->left, father);
	process(head->right, father);
}

 //方法二：递归实现
/*
step:   1)若head为空或head==no1或head==no2，则返回head
        2)若左右子树均不为空，就返回头
        3)若左子树为空就返回右子树
*/

Node* lowestAncestor(Node* head, Node* no1, Node* no2) {
	if (head == NULL || head == no1 || head == no2)
		return head;
	Node* left = lowestAncestor(head->left, no1, no2);
	Node* right = lowestAncestor(head->right, no1, no2);
	if (left != NULL && right != NULL)
		return head;
	return left != NULL ? left : right;//左右子树并不都有返回值
}