题目链接:236. 二叉树的最近公共祖先 - 力扣(LeetCode)
二叉树皆可递归,可以递归查找两个节点的所在地,如果两个节点一个在root的左子树一个在右子树,说明root就是公共祖先,并且因为是递归,root就是最近的,如果不是,往左右子树递归的时候返回来空的,那说明最近公共祖先在非空的一侧,如果root就是两个节点之一,那么就直接返回
class Solution {
public:
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
if (root == nullptr || root == p || root == q)
return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if (left == nullptr)
return right;
if (right == nullptr)
return left;
return root;
}
};