题解 | #在二叉树中找到两个节点的最近公共祖先#

二叉树后序遍历从底向上寻找 p 和 q 的最近公共祖先

    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // 递归出口条件：如果根节点为空，则返回 0 表示 p 和 q 没有最近公共祖先
        if (!root) return 0;
        // 递归出口条件：如果根节点的值为 p 或 q，则返回 p 或 q 本身（自己就是自己的最近公共祖先）
        if (root->val == p || root->val == q) return root->val;
        // 左：递归查找左子树中 p 和 q 的最近公共祖先
        auto left = lowestCommonAncestor(root->left, p, q);
        // 右：递归查找右子树中 p 和 q 的最近公共祖先
        auto right = lowestCommonAncestor(root->right, p, q);
        // 根：判断 left 和 right 是否为空，不为空则返回当前节点，否则返回另外一边
        if (!left) return right;
        if (!right) return left;
        return root->val;
    }