一、题目描述：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
二、输入输出实例：
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点5和节点1的最近公共祖先是节点3 。示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点5和节点4的最近公共祖先是节点5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3：
输入：root = [1,2], p = 1, q = 2 输出：1
三、先决知识点：
- 最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
四、思路讲解：
- 可以将这个问题转换为求两个节点路径分岔点的问题。
- 如上图，如果要求6和4的最近公共祖先，可以写出6的路径为(3->5->6)，4的路径为(3->5->2->4)。则他们的路径分叉点在5这个位置。
- 使用两个stack，分别存储两条路径，当求得两个两条路径后，将长的路径出栈至和短的路径大小相同。
- 然后开始比较，如果两个栈的栈顶的节点指针不同，则出栈，继续比较。因为这个问题的规定，所以一定存在分叉点。
五、C++代码：
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { stack<TreeNode*> ps,qs; getpath(root,p,ps); getpath(root,q,qs); while(ps.size()!=qs.size()) { if(ps.size()>qs.size()) ps.pop(); else qs.pop(); } while(ps.top()!=qs.top()) { ps.pop(); qs.pop(); } return ps.top(); } //查找路径，并存储到栈中。 bool getpath(TreeNode* root,TreeNode* p,stack<TreeNode*>& s) { if(root==nullptr)//如果指针为空，返回false return false; s.push(root);//指针不为空，压栈 if(root==p)//找到节点，路径结束，返回true return true; //如果路径未结束，递归左右子树 if(getpath(root->left,p,s))//如果左子树查找到路径，返回true return true; if(getpath(root->right,p,s))//如果右子树查找到路径，返回true return true; //丢弃返回的false，不用处理 如果到最后都没有找到，说明不在当前子树，出栈当前节点，并返回false s.pop(); return false; } };