//三叉鏈
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
	TreeNode *parent;
    TreeNode(int x) : val(x), left(NULL), right(NULL), parent(NULL) {}
};
class Solution {
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		TreeNode* curp = p, *curq = q; //用于遍歷p、q結(jié)點(diǎn)的祖先結(jié)點(diǎn)
		int lenp = 0, lenq = 0; //分別記錄p、q結(jié)點(diǎn)各自的祖先結(jié)點(diǎn)個(gè)數(shù)
		//統(tǒng)計(jì)p結(jié)點(diǎn)的祖先結(jié)點(diǎn)個(gè)數(shù)
		while (curp != root)
		{
			lenp++;
			curp = curp->parent;
		}
		//統(tǒng)計(jì)q結(jié)點(diǎn)的祖先結(jié)點(diǎn)個(gè)數(shù)
		while (curq != root)
		{
			lenq++;
			curq = curq->parent;
		}
		//longpath和shortpath分別標(biāo)記祖先路徑較長和較短的結(jié)點(diǎn)
		TreeNode* longpath = p, *shortpath = q;
		if (lenp < lenq)
		{
			longpath = q;
			shortpath = p;
		}
		//p、q結(jié)點(diǎn)祖先結(jié)點(diǎn)個(gè)數(shù)的差值
		int count = abs(lenp - lenq);
		//先讓longpath往上走count個(gè)結(jié)點(diǎn)
		while (count--)
		{
			longpath = longpath->parent;
		}
		//再讓longpath和shortpath同時(shí)往上走，此時(shí)第一個(gè)相同的結(jié)點(diǎn)便是最近公共祖先結(jié)點(diǎn)
		while (longpath != shortpath)
		{
			longpath = longpath->parent;
			shortpath = shortpath->parent;
		}
		return longpath; //返回最近公共祖先結(jié)點(diǎn)
	}
};

//搜索二叉樹
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if (p->val == root->val || q->val == root->val) //p、q結(jié)點(diǎn)中某一個(gè)結(jié)點(diǎn)的值等于根結(jié)點(diǎn)的值，則根結(jié)點(diǎn)就是這兩個(gè)結(jié)點(diǎn)的最近公共祖先
			return root;
		if (p->val < root->val&&q->val < root->val) //p、q結(jié)點(diǎn)的值都小于根結(jié)點(diǎn)的值，說明這兩個(gè)結(jié)點(diǎn)的最近公共祖先在該樹的左子樹當(dāng)中
			return lowestCommonAncestor(root->left, p, q);
		else if (p->val > root->val&&q->val > root->val) //p、q結(jié)點(diǎn)的值都大于根結(jié)點(diǎn)的值，說明這兩個(gè)結(jié)點(diǎn)的最近公共祖先在該樹的右子樹當(dāng)中
			return lowestCommonAncestor(root->right, p, q);
		else //p、q結(jié)點(diǎn)的值一個(gè)比根小一個(gè)比根大，說明根就是這兩個(gè)結(jié)點(diǎn)的最近公共祖先
			return root;
	}
};

//普通二叉樹
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
	bool Find(TreeNode* root, TreeNode* x)
	{
		if (root == nullptr) //空樹，查找失敗
			return false;
		if (root == x) //查找成功
			return true;

		return Find(root->left, x) || Find(root->right, x); //在左子樹找到了或是右子樹找到了，都說明該結(jié)點(diǎn)在該樹當(dāng)中
	}
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if (p == root || q == root) //p、q結(jié)點(diǎn)中某一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)，則根結(jié)點(diǎn)就是這兩個(gè)結(jié)點(diǎn)的最近公共祖先
			return root;
		//判斷p、q結(jié)點(diǎn)是否在左右子樹
		bool IspInLeft, IspInRight, IsqInLeft, IsqInRight;
		IspInLeft = Find(root->left, p);
		IspInRight = !IspInLeft;
		IsqInLeft = Find(root->left, q);
		IsqInRight = !IsqInLeft;

		if (IspInLeft&&IsqInLeft) //p、q結(jié)點(diǎn)都在左子樹，說明這兩個(gè)結(jié)點(diǎn)的最近公共祖先也在左子樹當(dāng)中
			return lowestCommonAncestor(root->left, p, q);
		else if (IspInRight&&IsqInRight) //p、q結(jié)點(diǎn)都在右子樹，說明這兩個(gè)結(jié)點(diǎn)的最近公共祖先也在右子樹當(dāng)中
			return lowestCommonAncestor(root->right, p, q);
		else //p、q結(jié)點(diǎn)一個(gè)在左子樹一個(gè)在右子樹，說明根就是這兩個(gè)結(jié)點(diǎn)的最近公共祖先
			return root;
	}
};

//普通二叉樹
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
	bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
	{
		if (root == nullptr)
			return false;
		path.push(root); //該結(jié)點(diǎn)可能是路徑當(dāng)中的結(jié)點(diǎn)，先入棧

		if (root == x) //該結(jié)點(diǎn)是最終結(jié)點(diǎn)，查找結(jié)束
			return true;

		if (FindPath(root->left, x, path)) //在該結(jié)點(diǎn)的左子樹找到了最終結(jié)點(diǎn)，查找結(jié)束
			return true;
		if (FindPath(root->right, x, path)) //在該結(jié)點(diǎn)的右子樹找到了最終結(jié)點(diǎn)，查找結(jié)束
			return true;

		path.pop(); //在該結(jié)點(diǎn)的左右子樹均沒有找到最終結(jié)點(diǎn)，該結(jié)點(diǎn)不可能是路徑當(dāng)中的結(jié)點(diǎn)，該結(jié)點(diǎn)出棧
		return false; //在該結(jié)點(diǎn)處查找失敗
	}
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		stack<TreeNode*> pPath, qPath;
		FindPath(root, p, pPath); //將從根到p結(jié)點(diǎn)的路徑存放到pPath當(dāng)中
		FindPath(root, q, qPath); //將從根到q結(jié)點(diǎn)的路徑存放到qPath當(dāng)中
		//longpath和shortpath分別標(biāo)記長路徑和短路徑
		stack<TreeNode*>* longPath = &pPath, *shortPath = &qPath;
		if (pPath.size() < qPath.size())
		{
			longPath = &qPath;
			shortPath = &pPath;
		}
		//讓longPath先彈出差值個(gè)數(shù)據(jù)
		int count = longPath->size() - shortPath->size();
		while (count--)
		{
			longPath->pop();
		}
		//longPath和shortPath一起彈數(shù)據(jù)，直到兩個(gè)棧頂?shù)慕Y(jié)點(diǎn)相同
		while (longPath->top() != shortPath->top())
		{
			longPath->pop();
			shortPath->pop();
		}
		return longPath->top(); //返回這個(gè)相同的結(jié)點(diǎn)，即最近公共祖先
	}
};