题解 | #农场牛群族谱#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目主要考察了二叉树的遍历和寻找两个节点的最近公共祖先。

题目解答方法的文字分析

要解决这道题目，我们需要找到给定两头牛的最近公共祖先。可以使用递归的方法来寻找。我们可以考虑以下几种情况：

1. 如果当前节点为空，直接返回0表示未找到。
2. 如果当前节点的值等于其中一个牛的值，那么当前节点就是最近公共祖先，直接返回当前节点的值。
3. 递归查找当前节点的左子树和右子树，分别得到左子树和右子树中两头牛的最近公共祖先。
4. 如果左子树的最近公共祖先和右子树的最近公共祖先都存在，说明两头牛分别在当前节点的左右子树中，那么当前节点就是最近公共祖先，直接返回当前节点的值。
5. 如果只在左子树中找到一个牛的祖先，说明最近公共祖先在左子树中，返回左子树的最近公共祖先。
6. 如果只在右子树中找到一个牛的祖先，说明最近公共祖先在右子树中，返回右子树的最近公共祖先。
7. 如果左右子树都没有找到牛的祖先，返回0表示未找到。

本题解析所用的编程语言

本题解析所用的编程语言是C++。

完整且正确的编程代码

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        if (!root) {
            return 0; // 返回0表示未找到
        }

        // 如果当前节点的值等于其中一个牛的值，那么当前节点就是最近公共祖先，直接返回当前节点的值。
        if (root->val == p || root->val == q) {
            return root->val;
        }

        int leftAncestor = lowestCommonAncestor(root->left, p, q);
        int rightAncestor = lowestCommonAncestor(root->right, p, q);

        // 如果左子树和右子树中各有一个牛，那么当前节点就是最近公共祖先，直接返回当前节点的值。
        if (leftAncestor && rightAncestor) {
            return root->val;
        }
        // 如果只在左子树中找到一个牛的祖先，说明最近公共祖先在左子树中，返回左子树的最近公共祖先。
        else if (leftAncestor) {
            return leftAncestor;
        }
        // 如果只在右子树中找到一个牛的祖先，说明最近公共祖先在右子树中，返回右子树的最近公共祖先。
        else if (rightAncestor) {
            return rightAncestor;
        }
        // 如果左右子树都没有找到牛的祖先，返回0表示未找到。
        else {
            return 0;
        }
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！