/**[][]
, 
 T  pq x x  pq  x 
:  root = [3,5,1,6,2,0,8,null,null,7,4]

 1:
: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
: 3
:  5  1  3

 2:
: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
: 5
:  5  4  5
 

:

pq 
*/

/*
1

null,null
pq,






*/
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //
        if(root == null || root == p || root == q) return root;
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if(left == null && right == null){
            return null;
        }else if(left != null && right != null){//p,q 
            return root;
        }else{
            return left != null ? left : right;
        }        
    }
}