//hh 1340ms应该没有比我更慢的了吧QAQ
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr) return root;
        if(p == nullptr || q == nullptr) return p ? p : q;
        if(has_node(root->left, p->val) && has_node(root->left, q->val)) {
            return lowestCommonAncestor(root->left, p, q);
        }
        else if(has_node(root->right, p->val) && has_node(root->right, q->val)) {
            return lowestCommonAncestor(root->right, p, q);
        }
        return root;
    }

    bool has_node(TreeNode* root, int val) {
        if(root == nullptr) return false;
        return root->val == val || has_node(root->left, val) || has_node(root->right, val);
    }
};