题目
LCR 194. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
例如，给定如下二叉树:
root = [3,5,1,6,2,0,8,null,null,7,4]
- 示例 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。因为根据定义最近公共祖先节点可以为节点本身。
- 说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。注意：本题与主站 236 题相同：LeetCode - Lowest Common Ancestor of a Binary Tree
解法
- 这题与 LCR193 的不同之处在于其不是二叉搜索树，故不能简单地用节点的大小值比较来找到目标节点，进而找到最近公共祖先
- 对可能的公共祖先进行分析，p/q可能就是最近的公共祖先，如下图，1 和 3 最近的公共祖先就是1
- 公共祖先也可能是根，如下图，目标节点 2 和 3 分布在 1 两侧，最近公共祖先就是 1
- 进行前序遍历，从顶至下，当找到第一个目标节点时就返回，由于是从顶往下找，第二个目标节点可能在第一个目标节点的下面，也可能在第一个目标节点的异侧
- 找到了第一个目标节点后，立刻返回，然后在目标节点的根的另一侧寻找第二个目标节点，如果找不到，则说明第二个目标节点和第一个目标节点在同一个子树上，所以最近公共祖先就是第一个目标节点。（比如下图，目标节点为2、4，找到 2 后立刻返回，在 2 的根 1 的另一边子树寻找 4，发现没有找到，则 4 一定在 2 这边的子树，所以 2 就是最近的公共祖先）
- 如果找到第一个目标节点后，在第一个目标节点的根的另一边可以找到第二个目标节点，则目标节点分布在根的两侧，此时由先序遍历可知，根就是最近的公共祖先。（比如下图，当找到第一个目标节点 2 之后，在 2 的根 1 的另一边找第二个节点 4，发现可以找到，则目标节点 2 和 4 分布在根 1 的两侧，所以根 1 就是最近的公共祖先）
作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/lh5kuh/
来源：力扣（LeetCode）
class Solution {
public:
//递归返回值：空节点/最近公共祖先节点（可能是自身也可能是上一个节点）
//递归工作：在当前节点的左右子树中寻找目标节点
//递归结束条件：越过子节点/找到了目标节点
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root || root==p || root==q) return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if(!left) return right;
if(!right) return left;
return root;
}
};
