一个服务器可以做两个网站吗,网站开发综合实训记录周记,server2008部署网站,呼市互联网公司排名问题描述#xff1a;给定一个二叉树#xff0c;判断其是否是一个有效的二叉搜索树#xff0c;假设一个二叉搜索树具有以下特征#xff1a;节点的左子树质保函小于当前节点的数#xff0c;节点的右子树质保函大于当前节点的数#xff0c;所有左子树和右子树本身也是二叉搜…问题描述给定一个二叉树判断其是否是一个有效的二叉搜索树假设一个二叉搜索树具有以下特征节点的左子树质保函小于当前节点的数节点的右子树质保函大于当前节点的数所有左子树和右子树本身也是二叉搜索树。
中序遍历求解对于一颗二叉搜索树而言其中序遍历结果是有序的。
递归方式求解定义一个全局的变量用于存储之前访问的那个元素只要中序遍历过程中小于这个值的话则表明不是二叉搜索树若大于这个pre则更新pre并进入下一次递归。
int preInteger.MIN_VALUE;
public Boolean isBinarySearch(TreeNode root)
{
if(rootnull){return true;}
Boolean leftisBinarySearch(root.left);
if(leftfalse){return false;}
if(root.valpre){return false;}
else
{
preroot.val;
return isBinarySearch(root.right);
}
}
public Boolean IsBinarySearch(TreeNode root)
{
return isBinarySearch(root);
}
将所有的结果都放入链表中最后来判断该链表是否是递增的若是则返回true若不是则返回false。
public void isBinarySearch(TreeNode root,ListTreeNodelist)
{
if(rootnull){return;}
isBinarySearch(root.left,list);
list.add(root);
isBinarySearch(root.right.list);
}
public Boolean IsBinarySearch(TreeNode root)
{ListTreeNodelistnew LinkedList();
isBinarySearch(root,list);
int prelist.get(0).val;
for(int i1;ilist.size();i)
{
if(list.get(i).valpre){return false;}
else
{
prelist.get(i).val;
}
}
return true;
}
递归求解通过一层层的遍历每个节点逐一判断
public Boolean isBinarySearch(TreeNode root)
{
if(root.leftnullroot.rightnull){return true;}
else if(root.leftnullroot.right!null)
{
if(root.right.valroot.val){return false;}
else{
return isBinarySearch(root.right);
}else if(root.left!nullroot.rightnull)
{
if(root.left.valroot.val){return false;}
else{
return isBinarySeach(roo.left);
}}else
{
if(!(root.leftroot.valroot.rightroot.val)){return false;}
else
{
return isBinarySearch(roo.left)isBinarySearch(root.right);
}}
}
}
非递归方式使用栈来求解后进栈的先处理符合树的求解过程
public Boolean isBinarySearch(TreeNode root)
{
TreeNode pre;
pre.valInteger.MIN_VALUE;
StackTreeNodestacknew Stack();
TreeNode currentroot;
while(current!null||stack!null)
{
while(current!null){stack.push();currentcurrent.left;}
currentstatck.pop();
if(current.valpre.val){return false;}
else{
precurrent;
currentcurrent.right;
}
}
return true;
}
