NC102 最近公共祖先

NC102 最近公共祖先

- 1、题目描述：

- 2、题目链接：
https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116?tpId=117&&tqId=35027&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking

-3、 设计思想：

详细操作流程看下图：

-5、代码：
c++版本:

 /**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    TreeNode* dfs(TreeNode* root,int o1,int o2){
        //如果当前节点为空，或者当前节点等于o1或者等于o2就返回值给父亲节点
        if(root == NULL || root->val == o1 || root->val == o2) return root;
        //递归遍历左子树
        TreeNode *left = dfs(root->left,o1,o2);
        //递归遍历右子树
        TreeNode *right = dfs(root->right,o1,o2);
        //如果left、right都不为空，那么代表o1、o2在root的两侧，所以root为他们的公共祖先
        if(left != NULL && right != NULL) return root;
        //如果left、right有一个为空，那么就返回不为空的哪一个
        return left != NULL? left : right;

    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
       return dfs(root,o1,o2)->val;
    }
};

Java版本：

import java.util.*;

    /*
     * public clas