/**
 * dfs 找 LCA. 只有一次查询，所以不需要 tarjan 或者 rmq
 * 个人感觉 rmq 好理解一些，dfs标号一下然后转化成区间最小值。( u v 之间最短路径上深度最小的节点)
 */


using namespace std;

/**
 * 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 *dfs(TreeNode *root, TreeNode* p, TreeNode *q) {
        if(!root)
            return NULL;
        if(root == p)
            return root;
        if(root == q)
            return root;
        TreeNode *u = dfs(root->left, p, q);
        TreeNode *v = dfs(root->right, p, q);
        if(u == NULL) {
            u = v; v = NULL;
        }
        if(v)
            return root;
        return u;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return dfs(root, p, q);
    }
};
