问题
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 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
提示：
- 树中节点数目在范围
[2, 105]内。 -109 <= Node.val <= 109- 所有
Node.val互不相同。 p != qp和q均存在于给定的二叉树中。
思路
找到节点所在的路径，形成一个链表，转换成链表的共同节点问题。
代码
class Solution {
public://最好把解决方案放到一个作用域中bool FindPath(stack<TreeNode*>& path, TreeNode* root, TreeNode* Xnode){if (root == nullptr)return false;path.push(root);if (root == Xnode)return true;if (FindPath(path, root->left, Xnode)) //最终要么找到（true)，要么走到空(false)return true;if (FindPath(path, root->right, Xnode))return true;//找不到该节点就不是路径之一，pop掉path.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> ppath;stack<TreeNode*> qpath;//找路径FindPath(ppath, root, p);FindPath(qpath, root, q);//跟普通链表思路一致//倒着删除使路径长度一致（对于栈而言，删除是倒着进行的）while (ppath.size() != qpath.size()){if (qpath.size() > ppath.size())qpath.pop();elseppath.pop();}//倒着删除路径，节点一致之后就是祖先while (ppath.top() != qpath.top()){qpath.pop();ppath.pop();}return qpath.top();}
};FindPath函数的理解
我们借助一个容器，来存放节点的指针。二叉树需要遍历时，核心就是对先序、中序、后序的变形应用！！！
这段代码是用来在二叉树中查找一个特定节点x的路径，并把这个路径存储在一个栈path中。下面是对代码逻辑的解释：
如果当前节点root是空的（即nullptr），那么意味着我们已经到达了树的末端还没有找到节点x，所以返回false。
将当前节点root压入栈path中。这是因为在递归的过程中，我们需要记录经过的路径。
检查当前节点root是否就是我们要找的节点x。如果是，那么我们已经找到了节点，此时路径栈path中存储的就是从根节点到节点x的路径，因此返回true。
如果当前节点不是节点x，那么递归地在左子树中查找节点x。如果在左子树中找到了节点x，那么函数会直接返回true，不需要执行后续的操作。
如果在左子树中没有找到节点x，那么递归地在右子树中查找节点x。如果在右子树中找到了节点x，同样函数会直接返回true。
如果左右子树中都没有找到节点x，那么说明当前节点root不在从根节点到节点x的路径上。因此，我们需要将root从栈path中弹出（path.pop()），因为这表示回溯到上一个节点，尝试其他的路径。
最后，返回false，表示在以root为根的子树中没有找到节点x。
为什么我们需要在返回false之前执行path.pop()？
这是因为栈path用于记录从根节点到当前节点root的路径。如果在当前节点的左右子树中都没有找到节点x，那么当前节点root不应该在从根节点到节点x的路径上，因此我们需要将它从栈中移除。
回溯是递归算法中的一个重要概念。在递归探索一个分支之后，如果该分支不满足条件（在这里是找不到节点x），我们需要撤销之前所做的操作（在这里是将节点加入路径栈），以便回到之前的状态，然后尝试其他的分支。
如果不执行path.pop()，那么栈path将包含不属于从根节点到节点x路径的节点，这将导致最终得到的路径是错误的
主体部分
//倒着删除使路径长度一致（对于栈而言，删除是倒着进行的）while (ppath.size() != qpath.size()){if (qpath.size() > ppath.size())qpath.pop();elseppath.pop();}//倒着删除路径，节点一致之后就是祖先while (ppath.top() != qpath.top()){qpath.pop();ppath.pop();}跟链表找公共祖先一样先删除的节点数目一致，然后再一起pop，知道出现节点相同。