/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*>  result;
    int find_node(TreeNode* cur, TreeNode* p, TreeNode* q)
    {
        int cur_val=0;
        if(cur==NULL) return 0;
        //找到p权值是1，找到q权值是2
        if(cur->val == p->val) cur_val += 1;
        if(cur->val == q->val) cur_val += 2;
        int left_val = find_node(cur->left , p, q);
        int right_val = find_node(cur->right , p, q);
    //当这个节点及左右子树里面满足3，也就是同时存在pq时候，存入vector
        if(left_val+right_val+cur_val==3) result.push_back(cur) ;
    //返回权值和
        return left_val+right_val+cur_val;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int val = find_node(root,p,q);
        //因为最进公共祖先最后发现，但是由于递归是最先存入vector，因此取第一个
        return result[0];
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* find_node(TreeNode* cur, TreeNode* p, TreeNode* q)
    {   
        //发现pq或者空，返回该节点
            if (cur == q || cur == p || cur == NULL) return cur;
            TreeNode* left = find_node(cur->left, p, q);
            TreeNode* right = find_node(cur->right, p, q);
            //发现两边均有点，返回当前点
            if (left != NULL && right != NULL) return cur;
      //发现右子树有点返回
            if (left == NULL && right != NULL) return right;
            //发现左子树有点返回
            else if (left != NULL && right == NULL) return left;
            else  return NULL;  //  (left == NULL && right == NULL)
        }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return find_node(root,p,q);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* result ;
    int track_back(TreeNode* cur, TreeNode* p, TreeNode* q)
    {
        if(cur == NULL) return 0;
        int flag = 0;
        int left_flag = track_back(cur->left , p ,q);
        int right_flag = track_back(cur->right , p ,q);
        if(cur == p) flag += 1;
        else if(cur == q ) flag += 2;
        if(flag + left_flag + right_flag == 3) 
        {
            result = cur;
            return 0;
        }
        return flag + left_flag + right_flag;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        track_back(root,p,q);
        return result;
    }
};