[LeetCode 236] 二叉树的最近公共祖先

本菜鸡能想到的方法MLE了
用例的树小的时候应该是可以过的，但就是因为俩vector导致MLE了QAQ

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
    public:
        int finish;
        void dfs(TreeNode *node,TreeNode *target,vector<TreeNode *> tmp,vector<TreeNode *> &res) {
            if(!node||finish)return;
            tmp.push_back(node);
            if(node==target) {
                res=tmp;
                finish=1;
                return;
            }
            dfs(node->left,target,tmp,res);
            dfs(node->right,target,tmp,res);
            tmp.pop_back();
        }
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            finish=0;
            vector<TreeNode *> tmp,res1,res2;
            dfs(root,p,tmp,res1);
            finish=0;
            dfs(root,q,tmp,res2);
            TreeNode *res=NULL;
            for(int i=0; i<res1.size()&&i<res2.size(); i++) {
                if(res1[i]==res2[i]){
                    res=res1[i];
                }else{
                    break;
                }
            }

            return res;
        }
};


int main() {
    TreeNode *a1 = new TreeNode(3);
    TreeNode *b1 = new TreeNode(5);
    TreeNode *b2 = new TreeNode(1);
    TreeNode *c1 = new TreeNode(6);
    TreeNode *c2 = new TreeNode(2);
    TreeNode *c3 = new TreeNode(0);
    TreeNode *c4 = new TreeNode(8);
    TreeNode *d1 = new TreeNode(7);
    TreeNode *d2 = new TreeNode(4);

    a1->left = b1;
    a1->right = b2;
    b1->left = c1;
    b1->right=c2;
    b2->left = c3;
    b2->right = c4;
    c2->left = d1;
    c2->right = d2;

    Solution s;
    TreeNode*res=s.lowestCommonAncestor(a1,c1,d2);
    cout<<res->val;


    return 0;
}

大佬的方法%%%

算是一时看懂了，主要在理解这行
return left == nullptr? right : (right == nullptr? left : root);
%%%%%%%

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q){return root; }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        return left == nullptr? right : (right == nullptr? left : root); //it's impossible that left and right are all nullptr
    }