判断一棵树是否是搜索二叉树
程序员文章站
2022-03-03 09:34:17
...
思路
二叉树中序遍历的结果是依次升序的,则该二叉树是搜索二叉树,否则不是。可在非递归的二叉树中序遍历中稍加修改。
代码
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static boolean isBST(Node head){
Stack<Node> stack =new Stack<>();
if (head == null) return true;
Node cur=head;
while (!stack.isEmpty() || cur!=null){
int pre=Integer.MIN_VALUE;
//当前节点不为空时入栈,当前节点指针指向左孩子
if (cur!=null){
stack.add(cur);
cur=cur.left;
}else {
cur=stack.pop();
//和前一个数比较
if (cur.value<pre){
return false;
}
pre=cur.value;
cur=cur.right;
}
}
return true;
}
上一篇: opencv之core模块
下一篇: 判断一棵树是否是完全二叉树