class Solution {
 public:
	 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
	 {
		 //如果当前子树中存在p或q则返回的找到的p或q节点
		 //为空表示当前子树没有p或q节点，返回空
		 if (!root || root == p || root == q) return root;
		 //去当前左子树中搜索，如果存在p或者q，就返回对应p或者q节点
		 //不存在返回空
		 TreeNode* left = lowestCommonAncestor(root->left, p, q);
		 //右子树同理
		 TreeNode* right = lowestCommonAncestor(root->right, p, q);
		 //p和q位于不同子树
		 if (left && right) return root;
		 //p和q位于同一子树
		 return left ? left : right;
	 }
 };

 class Solution {
 public:
	 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
	 {
		 if (root == NULL) return NULL;
		 map<TreeNode*,TreeNode*> ret;//存储对应节点和它的父亲节点
		 queue<TreeNode*>  que;
		 que.push(root);//根节点入队
		 ret[root] = NULL;//根节点没有父亲节点
		 //当两个节点都找到时，退出循环
		 while (ret.find(p)==ret.end()||ret.find(q)==ret.end())
		 {
			 TreeNode* temp=que.front();
			 que.pop();
			 if (temp->left)
			 {
				 //左子节点不为空，把它加入到队列中
				 que.push(temp->left);
				 //左子节点不为空，记录下他的父节点
				 ret[temp->left] = temp;
			 }
			 //右节点同上
			 if (temp->right)
			 {
				 que.push(temp->right);
				 ret[temp->right] = temp;
			 }
		 }
		 //寻找p和q的最近的公共祖先
		 set<TreeNode*> ancestor;
		 //记录下p和他的祖先节点，从p节点开始一直到根节点。
		 while (p)
		 {
			 ancestor.insert(p);
			 p = ret[p];
		 }
		 //查看p和他的祖先节点是否包含q节点，如果不包含再看是否包含q的父节点……
		 while (ancestor.end()==ancestor.find(q))
			 q = ret[q];
		 return q;
	 }
 };