TOP10题解 |BM38#二叉树中两个节点的最近公共祖先#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.04
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief   对于普通二叉树寻找两个节点的最近公共祖先，可以通过递归的方式来解决。对于当前节点，有以下几种情况：
 *  (一)如果当前节点的值等于其中一个目标节点的值（o1或o2），则当前节点即为最近公共祖先节点(自己可以是自己的祖先)。
 *  (二)如果当前节点的值不等于任何目标节点的值，则需要分别递归查找其左子树和右子树。
 *      ①如果左子树返回不为空，右子树返回也不为空，则说明目标节点分布在当前节点的两侧，当前节点即为最近公共祖先节点。
*       ②如果左子树返回的结果为空，说明目标节点都在右子树中，返回右子树的结果即可。
*       ③如果右子树返回的结果为空，说明目标节点都在左子树中，返回左子树的结果即可。
 * @param root TreeNode类 
 * @param o1 int整型 
 * @param o2 int整型 
 * @return int整型
 */

int lowestCommonAncestor(struct TreeNode* root, int o1, int o2 ) 
{
    // write code here
    if(root == NULL)
    {
        return 0;
    }

    if(root->val == o1 || root->val == o2)
    {
        return root->val;
    }

    int leftResult = lowestCommonAncestor(root->left, o1, o2);
    int rightResult = lowestCommonAncestor(root->right, o1, o2);

    if(leftResult && rightResult)
    {
        return root->val;
    }

    return leftResult? leftResult: rightResult;
            
}