class CommonAncestorSearch {

	public static TreeNode<Integer> searchCommonAncestor(TreeNode<Integer> root, TreeNode<Integer> p, TreeNode<Integer> q){
		// 确保p和q都是root的子孙节点
		if(!isDescendant(root, p) || !isDescendant(root, q)){
			return null;
		}
		
		if(root == q || root== q){
			return root;
		}
		
		boolean is_p_on_left = isDescendant(root.left, p);
		boolean is_q_on_left = isDescendant(root.left, q);
		
		// 如果p和q在root的两边,则返回root
		if(is_p_on_left != is_q_on_left){
			return root;
		}
		
		// 如果p和q在root的同一边,则遍历访问那一边
		TreeNode<Integer> treeSide = is_p_on_left?root.left:root.right;
		return searchCommonAncestor(treeSide, p, q);
	}

}