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

class Solution {
public:
/**
 * 
 * @param root TreeNode类 
 * @param o1 int整型 
 * @param o2 int整型 
 * @return int整型
 */
void func(TreeNode* root, int o1, vector<TreeNode*> &path,vector<TreeNode*> &result, int falg)
{
    //结束条件
    if(!root || falg)
    {
        return;
    }
    //存入到临时容器中
    path.push_back(root);
    //找到了
    if(root->val == o1)
    {
        //将临时容器的值赋给最终结果容器
        falg = 1;
        result = path;
    }
    //继续递归
    func(root->left,  o1, path,result, falg);
    func(root->right, o1, path,result, falg);
    //没有的话删除最后进来的
    path.pop_back();
}
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
    // write code here
    //存放o1路径
    vector<TreeNode*> p1;
    //存放o2路径
    vector<TreeNode*> p2;
    //临时存放容器
    vector<TreeNode*> path;
    //标志位表示找到了，直接结束递归
    int falg = 0;
    //查找o1路径
    func(root, o1, path,p1, falg);
    //清楚临时容器
    path.clear();
    //查找o2路径
    func(root, o2, path,p2, falg);
    //比较俩路劲的长度，选择短的一段
    int len = 0;
    if(p1.size() < p2.size())
    {
        len = p1.size();
    }
    else{
        len = p2.size();
    }
    //比较值，得到最先出现的相同数字，即为最近公共祖先
    TreeNode* result ;
    for(int i = 0; i < len; i++)
    {
        if(p1[i] == p2[i])
        {
            result = p1[i];
        }
    }
    return result->val;
}

};