难度： 中等
题目：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
解题：
递归
这道题可以看作二叉树后序遍历的变形，从使用递归底部网上走，判断每个子树（叶子节点可以看作没有孩子的子树）是否包含目标节点。
class Solution {
public:
// 返回空表示不包含目标节点，当前节点是返回当前节点（非空），表示包含目标节点
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr)
return nullptr;
// 从底向上来找
// 当前节点与目标节点相等，就是要返回的值
if(root == p || root == q)
return root;
TreeNode *pLeft = lowestCommonAncestor(root->left,p,q);
TreeNode *pRight = lowestCommonAncestor(root->right,p,q);
if(pLeft && pRight)
// 如果左子树右子树均不为空，当前节点就是最终节点
return root;
else
// 返回非空节点，若都为空，则返回空，表示两棵子树都不包含目标节点
return pLeft?pLeft:pRight;
}
};
存储父节点
也可采用存储父节点的方式。
class Solution {
public:
unordered_map<int, TreeNode*> fa;
unordered_map<int, bool> vis;
void dfs(TreeNode* root){
if (root->left != nullptr) {
fa[root->left->val] = root;
dfs(root->left);
}
if (root->right != nullptr) {
fa[root->right->val] = root;
dfs(root->right);
}
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
fa[root->val] = nullptr;
// 前序遍历存储父节点指针
dfs(root);
// 先遍历一遍其中一个目标节点的路径
while (p != nullptr) {
vis[p->val] = true;
p = fa[p->val];
}
// 遍历另一个找到重合节点
while (q != nullptr) {
// 访问过表示，该节点是最终答案
if (vis[q->val]) return q;
// 使这个指针指向它的父节点
q = fa[q->val];
}
return nullptr;
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。