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

dfs的运用

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param o1 int整型 
 * @param o2 int整型 
 * @return int整型
 */
#define MAXSIZE 100000
//dfs的运用
bool flag = false;
int count = 0;
void dfs(struct TreeNode* root,struct TreeNode** treenode,int temp){
    //找到或者还没到null，直接返回
    if(flag||root == NULL) return;
    //记录该路径
    treenode[count++] = root;
    //找到flag为true不再操作
    if(root->val == temp){
        flag = true;
        return;
    }

    dfs(root->left,treenode,temp);
    dfs(root->right,treenode,temp);
    //已经找到，直接返回
    if(flag) return;
    count--;
}
int lowestCommonAncestor(struct TreeNode* root, int o1, int o2 ) {
    // write code here
    //开辟空间
    struct TreeNode** treenode1 = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*MAXSIZE);
    struct TreeNode** treenode2 = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*MAXSIZE);
    for(int i = 0;i<MAXSIZE;i++){
        treenode1[i] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        treenode2[i] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    }
    int count1 = 0;
    int count2 = 0;
    int resul;
    dfs(root,treenode1,o1);
    count1 = count;
    count = 0;
    flag = false;
    dfs(root,treenode2,o2);
    count2 = count;
    //获取最近公共祖先
    for(int i = 0;i<=count1&&i<=count2;i++){
        if(treenode1[i]->val == treenode2[i]->val){
            resul = treenode1[i]->val;
        }else break;
    }
    return resul;
}