剑指68-II：二叉树的最近公共祖先

传送门

leetcode

题目描述

普通二叉树，在左右子树中查找是否存在 p 或者 q，
如果 p 和 q 分别在两个子树中，那么说明根节点就是最近公共祖先。

C++ 代码 - leetcode

/*
    经典问题，递归函数的定义：输入三个参数 root，p，q，它会返回一个节点。

    情况 1：
        若 p 和 q 都在以 root 为根的树，
        则 left 和 right 一定分别是 p 和 q。
    情况 2：
        若 p 和 q 都不在以 root 为根的树，
        则直接返回 null。
    情况 3：
        若 p 和 q 只有一个存在于 root 为根的树，
        则返回该节点。
*/
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // base case
        if (!root) return nullptr;
        if (root == p || root == q) return root;

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        // case 1
        if (left != nullptr && right != nullptr) {
            return root;
        }
        // case 2
        if (left == nullptr && right == nullptr) {
            return nullptr;
        }
        // case 3
        return left == nullptr ? right : left;
    }
};