121 二叉搜索树的最近公共祖先

问题描述：给定一个二叉搜索树，找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：对于有根树T的两个节点p、q，最近公共祖先表示为一个节点x，满足x是p和q的祖先，且x的深度尽可能大。

非递归求解：只要找到取值在p和q中间的那个节点即可。如果遍历过程中只要节点小于p和q任意一个，则在右节点中找，如果节点大于p和q中任意一个，则在左节点中找。

public TreeNode ancester(TreeNode root,TreeNode p1,TreeNode p2)
{
int minNumber=Math.min(p1.val,p2.val);
int maxNumber=Math.max(p1.val,p2.val);
TreeNode current=root;
while(true)
{
if(current.val<maxNumber&&current.val>minNumber)
{
return current;
}
if(current.val<min)
{
current=current.right;
}
if(current.val>max)
{
current=current.left;
???????}
}
}

递归方式求解

public TreeNode dfs(TreeNode root,TreeNode p,TreeNode q)
{
if(root.val<Math.max(p.val,q.val)&&root.val>Math.min(p.val,q.val)){return root;}
if(root.val<Math.min(p.val,q.val)){return dfs(root.right,p,q);}
if(root.val>Math.max(p.val,q.val)){return dfs(root.left,p,q);}
}