class Solution {
    
    private TreeNode res = null;
    
    public boolean dfs(TreeNode root,TreeNode p,TreeNode q){
        if(root==null){
            return false;
        }

        boolean lchild = dfs(root.left,p,q);
        boolean rchild = dfs(root.right,p,q);

        if((lchild&&rchild)||((root.val==p.val||root.val==q.val)&&(lchild||rchild))){
            res = root;
        }

        return lchild||rchild||(root.val==p.val||root.val==q.val);
    }

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