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

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

class Solution {
public:
    
    void trs(TreeNode* root, int val, vector<int>& v1, bool &find){
        if(root&&root->val==val) find = true;
        if(!find&&root->left) trs(root->left,val, v1, find);
        if(!find&&root->right) trs(root->right,val, v1, find);
        if(find) v1.push_back(root->val);
    }
    
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        vector<int> v1,v2;
        bool find=false;
        int ans=0x3f3f3f3f;
        
        trs(root, o1, v1, find);
        find = false;
        trs(root, o2, v2, find);
        int sz1 = v1.size(), sz2 = v2.size();

        for(int i=0,j=0; i<sz1, j<sz2; i++,j++){
            if(v1.back()!=v2.back()) break;
            ans = v1.back();
            v1.pop_back();
            v2.pop_back();
        }
        return ans;
    }
};