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

递归的思路要能想到，然后就是深度优先搜索后获得公共的祖先，注意祖先包括自身， 真祖先才不包括自己，概念需要复习一下

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
#include <stack>
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    void traverse(TreeNode* node, int o1, int o2, vector<int>& temp, vector<vector<int>>& res){
        temp.push_back(node->val);
        if(node->val == o1 or node->val == o2){
            vector<int>* t = new vector<int>(temp);
            res.push_back(*t);
            if(res.size() == 2){
                return ;
            }
        }
        
        if(node->left != NULL){
            traverse(node->left, o1, o2, temp, res);
        }
        if(node->right != NULL){
            traverse(node->right, o1, o2, temp, res);
        }
        temp.pop_back();
    }
    int recursion(TreeNode* root, int o1, int o2){
        int res = -1;
        if(root == NULL)
            return res;
        if(root->val == o1 or root->val == o2)
            res = root->val;
        int l = recursion(root->left, o1, o2);
        int r = recursion(root->right, o1 , o2);
        if(res != -1)
            return res;
        else{
            if(l != -1 and r != -1)
                return root->val;
            else if(l != -1)
                return l;
            else
                return r;
        }
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        vector<int> temp;
        vector<vector<int>> res;
//         traverse(root, o1, o2, temp, res);
//         assert(res.size() == 2);
//         vector<int> res1 = res[0];
//         vector<int> res2 = res[1];
//         int r = -1;
//         for(int i = res1.size() - 1; i >= 0; i--){
//             int val = res1[i];
//             for(int j = res2.size() - 1; j >= 0; j--){
//                 if(res2[j] == val){
//                     r = val;
//                     break;
//                 }
//             }
//             if(r != -1){
//                 break;
//             }
//         }
//         return r;
        return recursion(root, o1, o2);
    }
};