[编程题]BST判定

##### 输入描述:
`第一行：根节点键值;第二行开始，二叉树的结构，每行代表一组根节点与左右子节点的对应关系，-1代表空节点。格式：根节点键值:左子节点键值|右子节点键值例如，5:3|-1表示键值为5的节点，左子节点的键值为3,右子节点为空节点假设：所有节点的键值非负，且不超过1023`

##### 输出描述:
`判断结果，0表示输入不是二分查找树，1表示输入是二分查找树`

```5
5:4|7
4:3|8
7:2|-1
3:-1|-1
8:-1|-1
2:-1|-1```

## 输出

`0`
```import java.util.LinkedList;
import java.util.Scanner;

class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}

/**
* 如果BST是正确的，那么在进行中序遍历时，结点值应该是递增的
*
* @author wylu
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
TreeNode root = new TreeNode(scanner.nextInt());

queue.offer(root);
while (!queue.isEmpty()) {
TreeNode curRoot = queue.poll();
String str = scanner.next();
int left = Integer.valueOf(str.substring(str.indexOf(':') + 1, str.indexOf('|')));
int right = Integer.valueOf(str.substring(str.indexOf('|') + 1));

if (left != -1) {
curRoot.left = new TreeNode(left);
queue.offer(curRoot.left);
}
if (right != -1) {
curRoot.right = new TreeNode(right);
queue.offer(curRoot.right);
}
}
int res = isBinarySearchTree(root, new int[1]) ? 1 : 0;
System.out.println(res);
}

private static boolean isBinarySearchTree(TreeNode root, int[] curMax) {
if (root == null) return true;

if (root.left == null) return true;
if (root.left.val > root.val || !isBinarySearchTree(root.left, curMax)) return false;
//如果左子树的最大值比当前根结点的值大
if (curMax[0] > root.val) return false;

if (root.right == null) return true;
if (root.right.val < root.val || !isBinarySearchTree(root.right, curMax)) return false;

//更新已遍历结点的最大值
curMax[0] = Math.max(curMax[0], root.right.val);
return true;
}
} ```

```#include <bits/stdc++.h>

using namespace std;

int pre=-1,now=-1;

struct Tree{     int val,left,right;
};

void InOrder(Tree *T, int r)
{     if(r==-1)         return;              if(T[r].left != -1)         InOrder(T, T[r].left);          now = r;     if(now>pre)         pre = now;     else{         cout<<0<<endl;         return;     }          if(T[r].right!=-1)         InOrder(T, T[r].right);
}

int main()
{     int r;     while(cin>>r)      {         Tree T[100003];         int isBST = 1;         queue<int> q;         q.push(r);         int t,left,right;         char c;         do{             cin>>t>>c>>left>>c>>right;             T[t].val = t;             T[t].left = left;             T[t].right = right;                          q.pop();             if(left!=-1)             {                 q.push(left);                 if(left>t)                      isBST = 0;             }             if(right!=-1)             {                 q.push(right);                 if(right<t)                     isBST = 0;             }         }while(!q.empty());          if(isBST==0)             cout<<isBST<<endl;         else{             InOrder(T,r);         }     }     return 0;
}

```

```import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
public static void main(String [] args) {

Scanner sc = new Scanner(System.in);

// 输入int,代表根节点，要注意跳过最后一个换行符
int n = sc.nextInt();
TreeNode root = new TreeNode(n);
sc.nextLine();

// 利用队列构造树
queue.offer(root);
while (!queue.isEmpty()) {

// 取出一个节点
TreeNode curRoot = queue.poll();

// 首先得到该节点的左右节点的值
String str = sc.nextLine();
int left = Integer.valueOf(str.substring(str.indexOf(':') + 1, str.indexOf('|')));
int right = Integer.valueOf(str.substring(str.indexOf('|') + 1));

if (left != -1) {
curRoot.left = new TreeNode(left);
queue.offer(curRoot.left);
}

if (right != -1) {
curRoot.right = new TreeNode(right);
queue.offer(curRoot.right);
}
}

// 判断该树是否为二叉搜索树
isTree(root);
int result = isBinarySearchTree() ? 1 : 0;
System.out.println(result);
}

// 创建一个List，保存其中序遍历
static List<Integer>  list = new ArrayList<>();
private static void isTree(TreeNode root){
if(root == null)  return;
isTree(root.left);
isTree(root.right);
}

// 判断该List是不是递增
private static boolean isBinarySearchTree() {
for (int i = 0; i < list.size()-1; i++){
if (list.get(i) > list.get(i+1)){
return false;
}
}
return true;
}

}```

```import sys def preorder(res,root,new): if root!="-1":
preorder(res,res[root][0],new)
new.append(root)
preorder(res,res[root][1],new)
root=input()
res={} while(True):
res[key]=value.split("|")
new=[] #print(res) preorder(res,root,new)
flag=1 for i in range(1,len(new)): if new[i]<new[i-1]:
flag=0 if flag==1: print(1) else: print(0)```

4条回答 628浏览

# 通过挑战的用户

• 2019-07-23 19:16:08
• 2019-07-22 17:13:54
• 2019-07-16 13:32:19
• 2019-07-15 17:26:57
• 2019-07-10 19:59:12

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题