129 验证二叉搜索树

问题描述：给定一个二叉树，判断其是否是一个有效的二叉搜索树，假设一个二叉搜索树具有以下特征：节点的左子树质保函小于当前节点的数，节点的右子树质保函大于当前节点的数，所有左子树和右子树本身也是二叉搜索树。

中序遍历求解：对于一颗二叉搜索树而言，其中序遍历结果是有序的。

递归方式求解：定义一个全局的变量用于存储之前访问的那个元素，只要中序遍历过程中小于这个值的话，则表明不是二叉搜索树，若大于这个pre，则更新pre，并进入下一次递归。

int pre=Integer.MIN_VALUE;
public Boolean isBinarySearch(TreeNode root)
{
if(root==null){return true;}
Boolean left=isBinarySearch(root.left);
if(left==false){return false;}
if(root.val<pre){return false;}
else
{
pre=root.val;
return isBinarySearch(root.right);
}
}
public Boolean IsBinarySearch(TreeNode root)
{
return isBinarySearch(root);
}

将所有的结果都放入链表中，最后来判断该链表是否是递增的，若是则返回true，若不是，则返回false。

public void isBinarySearch(TreeNode root,List<TreeNode>list)
{
if(root==null){return;}
isBinarySearch(root.left,list);
list.add(root);
isBinarySearch(root.right.list);
}
public Boolean IsBinarySearch(TreeNode root)
{

List<TreeNode>list=new LinkedList<>();
isBinarySearch(root,list);
int pre=list.get(0).val;
for(int i=1;i<list.size();i++)
{
if(list.get(i).val<pre){return false;}
else
{
pre=list.get(i).val;
}
}
​​​​​​​return true;
}

递归求解：通过一层层的遍历每个节点逐一判断

public Boolean isBinarySearch(TreeNode root)
{
if(root.left==null&&root.right==null){return true;}
else if(root.left==null&&root.right!=null)
{
if(root.right.val<root.val){return false;}
else{
return isBinarySearch(root.right);
}else if(root.left!=null&&root.right==null)
{
if(root.left.val>root.val){return false;}
else{
return isBinarySeach(roo.left);
}

}else
{
if(!(root.left<root.val&&root.right>root.val)){return false;}
else
{
return isBinarySearch(roo.left)&&isBinarySearch(root.right);
​​​​​​​}

}
}
}

非递归方式使用栈来求解，后进栈的先处理，符合树的求解过程，

public Boolean isBinarySearch(TreeNode root)
{
TreeNode pre;
pre.val=Integer.MIN_VALUE;
Stack<TreeNode>stack=new Stack<>();
TreeNode current=root;
while(current!=null||stack!=null)
{
while(current!=null){stack.push();current=current.left;}
current=statck.pop();
if(current.val<pre.val){return false;}
else{
pre=current;
current=current.right;
}
}
​​​​​​​return true;
}