首页 > 试题广场 >

BST判定

[编程题]BST判定

热度指数：838 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

判断给定的二叉树是否为二分查找树。假设树的每个节点以整数为键值，且不同节点的键值互不相等。二分查找树成立的判定条件：

对任何非叶子节点A，如果A存在左子树，则A的键值大于其左子树所有节点的键值，且，如果A存在右子树，则A的键值小于其右子树所有节点的键值

输入描述:

第一行：根节点键值;

第二行开始，二叉树的结构，每行代表一组根节点与左右子节点的对应关系，-1代表空节点。格式：

根节点键值:左子节点键值|右子节点键值

例如，

5:3|-1

表示键值为5的节点，左子节点的键值为3,右子节点为空节点

假设：所有节点的键值非负，且不超过1023

输出描述:

判断结果，0表示输入不是二分查找树，1表示输入是二分查找树

示例1

输入

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

输出

算法知识视频讲解

勇敢牛牛，不怕困难！

#include <stdio.h>
#include <stdlib.h>

#define INF 0x3F3F3F3F
#define IsValidBST(infos, key) __IsValidBST(infos, key, -INF, +INF)

// ========== 二叉树节点信息表 ========== 
typedef int Key;
typedef struct {
  Key key;
  Key l_child, r_child;
} BST_NODE_INFO, *INFO;
// ========== 二叉树节点信息表 ========== 

int __IsValidBST(INFO infos, Key key, Key low, Key high) {
  if (key == -1) return 1;
  return key > low && key < high
      && __IsValidBST(infos, (infos + key)->l_child, low, key)
      && __IsValidBST(infos, (infos + key)->r_child, key, high);
}

int main(const int argc, const char* const argv[]) {
  
  BST_NODE_INFO infos[1000];
  Key root_key;
  fscanf(stdin, "%d", &root_key);
  
  Key fa, l_ch, r_ch;
  while (fscanf(stdin, "%d:%d|%d", &fa, &l_ch, &r_ch) != EOF) {
    (infos + fa)->key = fa;
    (infos + fa)->l_child = l_ch;
    (infos + fa)->r_child = r_ch;
  }
     
  return fprintf(stdout, "%d\n", IsValidBST(infos, root_key)), 0;
}

发表于 2021-08-13 11:40:59 回复(0)

pein531

中规中矩的解法，先重构二叉树，再检查其中序遍历是不是递增序列

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

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

public class Main {
    static ArrayList<Integer> inorderSeq = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeKey = Integer.parseInt(br.readLine().trim());
        // 重构二叉树
        TreeNode tree = new TreeNode(nodeKey);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(tree);
        while(!queue.isEmpty()){
            TreeNode curRoot = queue.poll();
            String str = br.readLine().trim();
            int left = Integer.parseInt(str.substring(str.indexOf(':') + 1, str.indexOf('|')));
            int right = Integer.parseInt(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);
            }
        }
        System.out.println(isBST(tree));
    }
    
    private static int isBST(TreeNode root) {
        inorder(root);
        for(int i = 1; i < inorderSeq.size(); i++)
            if(inorderSeq.get(i) <= inorderSeq.get(i - 1)) return 0;
        return 1;
    }
    
    private static void inorder(TreeNode root) {
        if(root == null) return;
        isBST(root.left);
        inorderSeq.add(root.val);
        isBST(root.right);
    }
}

编辑于 2021-04-10 11:26:56 回复(0)

C/C++

nbgao

#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;
}

发表于 2019-01-11 20:13:13 回复(0)

wylu

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());

        LinkedList<TreeNode> queue = new LinkedList<>();
        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;
    }
}

编辑于 2019-01-16 10:35:50 回复(0)

小小米稻

同样是中序遍历，提供一个非递归解法

#include<bits/stdc++.h>
using namespace std;

int main(){
    int root = 0;
    scanf("%d", &root);
    vector<vector<int>> tree(1024, {0,0});
    int father, left, right;
    while(scanf("%d:%d|%d", &father, &left, &right)!=EOF){
        tree[father][0] = left;
        tree[father][1] = right;
    }
    stack<int> stk;
    int cur=root, pre=-1, res=1;
    while(cur!=-1 || !stk.empty()){
        while(cur!=-1){
            stk.push(cur);
            cur = tree[cur][0];
        }
        cur = stk.top(); stk.pop();
        if(cur < pre){
            res = 0;
            break;
        }else{
            pre = cur;
        }
        cur = tree[cur][1]; // move to right
    }
    printf("%d\n", res);
    return 0;
}

发表于 2019-08-21 20:51:34 回复(0)

小谷围做题家

package main

import (
    "fmt"
    "os"
    "bufio"
    "strings"
    "strconv"
)

var in=bufio.NewReader(os.Stdin)

type Node struct{
    val int
    left *Node
    right *Node
}

func main() {
    var x int
    fmt.Scan(&x)
    root:=&Node{val:x}
    cnt:=map[int]*Node{x:root}
    var s string
    for{
        _,ok:=fmt.Fscan(in,&s)
        if ok!=nil{
            break
        }
        ss:=strings.Split(s,":")
        lr:=strings.Split(ss[1],"|")
        a,b,c:=atoi(ss[0]),atoi(lr[0]),atoi(lr[1])
        var node,l,r *Node
        if _,ok:=cnt[a];ok{
            node=cnt[a]
        }else{
            node=&Node{val:a}
            cnt[a]=node
        }
        if b!=-1{
            if _,ok:=cnt[b];ok{
                l=cnt[b]
            }else{
                l=&Node{val:b}
                cnt[b]=l
            }
        }
        if c!=-1{
            if _,ok:=cnt[c];ok{
                r=cnt[c]
            }else{
                r=&Node{val:c}
                cnt[c]=r
            }
        }
        node.left=l
        node.right=r
    }
    arr:=order(root)
    for i,x:=range arr{
        if i>0&&arr[i-1]>x{
            fmt.Print(0)
            return
        }
    }
    fmt.Print(1)
}

func atoi(s string)int{
    x,_:=strconv.Atoi(s)
    return x
}

func order(root *Node)[]int{
    if root==nil{
        return nil
    }
    ans:=[]int{}
    ans=append(ans,order(root.left)...)
    ans=append(ans,root.val)
    ans=append(ans,order(root.right)...)
    return ans
}

发表于 2023-03-18 13:17:50 回复(0)

C++

LeonChao

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cstdio>
#include <climits>

using namespace std;

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode():val(0), left(nullptr), right(nullptr){}
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};

TreeNode* reconstruct(int x, unordered_map<int, pair<int, int>>& hash){
    if(x == -1){
        return nullptr;
    }
    TreeNode* root = new TreeNode(x);
    root->left = reconstruct(hash[x].first, hash);
    root->right = reconstruct(hash[x].second, hash);
    return root;
}

bool isBST(TreeNode* root, int l, int r){
    if(!root){
        return true;
    }
    if(root->val<l || root->val>r){
        return false;
    }
    return isBST(root->left, l, root->val) && isBST(root->right, root->val, r);
}

int main(){
    // process input
    int node, left, right;
    unordered_map<int, pair<int, int>> hash;
    cin >> node;
    int root_val = node;
    while(scanf("%d:%d|%d", &node, &left, &right)!=EOF){
        hash[node] = {left, right};
    }
    // reconstruct binary tree
    TreeNode* root = reconstruct(root_val, hash);
    // BST
    int res = isBST(root, INT_MIN, INT_MAX);
    cout << res <<endl;
    return 0;
}

二叉树重构能单独出道题了。。。

发表于 2021-12-30 16:42:05 回复(0)

苏南霖

原理上还是二叉排序树的中序遍历结果是递增数列，胜在代码量比较少，利用数组建树遍历

import java.util.*;

public class Main{
    public static int pre = 0;
    public static boolean con = true;
    public static void inOrder(ArrayList<Integer> tree,int i,int len){
        if(i<len&&tree.get(i)!=-1&&con){
            inOrder(tree,2*i,len);
            if(tree.get(i)<pre){
                con = false;
            };
            pre = tree.get(i);
            inOrder(tree,2*i+1,len);
        }
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        ArrayList<Integer> tree = new ArrayList<>();
        int count = 1;
        in.nextLine();
        while(in.hasNext()){
            String line = in.nextLine();
            if(count==1){
                tree.add(Integer.parseInt(line.split(":")[0]));
                count++;
            }            
            String tmp = line.split(":")[1];
            tree.add(Integer.parseInt(tmp.split("\\|")[0]));
            tree.add(Integer.parseInt(tmp.split("\\|")[1]));
            count+=2;
        }
        inOrder(tree,1,count);
        System.out.println(con?1:0);
    }
}

发表于 2021-04-13 17:03:04 回复(0)

canikissyou

import java.util.Scanner;
import java.util.LinkedList;
class TreeNode{
    int val;
    TreeNode left=null;
    TreeNode right=null;
    
    public TreeNode(int val){
        this.val=val;
    }
}
public class Main{
    public static void mid(TreeNode root,LinkedList<Integer> seq){
        if(root!=null){
            mid(root.left,seq);
            seq.add(root.val);
            mid(root.right,seq);
        }
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        LinkedList<TreeNode> queue=new LinkedList();
        TreeNode root=new TreeNode(Integer.valueOf(sc.nextLine()));
        queue.add(root);
        while(queue.size()>0){
            TreeNode cur=queue.removeFirst();
            int[] nums=new int[3];
            int cnt=0;
            for(String str : sc.nextLine().split("[:\\|]")){
                nums[cnt++]=Integer.valueOf(str);
            }
            
            if(nums[1]!=-1){//左子树
                cur.left=new TreeNode(nums[1]);
                queue.add(cur.left);
            }
            
            if(nums[2]!=-1){//右子树
                cur.right=new TreeNode(nums[2]);
                queue.add(cur.right);
            }
        }
        LinkedList<Integer> seq=new LinkedList();
        mid(root,seq);
        int pre=-1;
        boolean flag=false;
        for(int num : seq){
            if(num<pre){
                break;
            }
            pre=num;
        }
        if(flag)
            System.out.println(1);
        else   
            System.out.println(0);
    }
}

发表于 2020-07-30 22:35:41 回复(0)

C/C++

哪里来的憨憨

//先构建二叉树，再判断该二叉树是否为BST

# include<iostream>

# include<unordered_map>
# include<vector>
using namespace std;

struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

bool validbst(TreeNode* root,TreeNode* &pre){
if(root==nullptr)
return true;
if(!validbst(root->left,pre))
return false;
if(pre&&root->val<=pre->val)
return false;
pre=root;
if(!validbst(root->right,pre))
return false;
return true;
}

int main(){
vector<int> res;
unordered_map<int,TreeNode*> m;
int rot;
int r,le,rig;
char c1,c2;
TreeNode* root;
TreeNode* rr;
TreeNode* ll;
TreeNode* pre=nullptr;
cin>>rot;
TreeNode* root1=new TreeNode(rot);
m[rot]=root1;
while(cin>>r>>c1>>le>>c2>>rig){
if(m.find(r)==m.end()){
root=new TreeNode(r);
m[r]=root;
}
if(m.find(le)==m.end()){
ll=new TreeNode(le);
m[le]=ll;
}
if(m.find(rig)==m.end()){
rr=new TreeNode(rig);
m[rig]=rr;
}
if(le!=-1)
m[r]->left=m[le];
if(rig!=-1)
m[r]->right=m[rig];
}
cout<<(validbst(root1,pre))?1:0;
return 0;
}

发表于 2020-07-17 10:56:03 回复(0)

Python

白色纯度

这道题目的测试样例太差劲了。只要输出是0，就通过了？这种操作也是醉了！

print(0)

发表于 2019-09-07 21:43:04 回复(1)

Java

菜鸡🐔🐔

import java.util.ArrayList;
import java.util.LinkedList;
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();

        // 利用队列构造树
        LinkedList<TreeNode> queue = new LinkedList<>();
        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);
        list.add(root.val);
        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;
    }

}

发表于 2019-05-28 09:58:31 回复(0)

猎户座1

估计我写的太复杂了

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):
    line=sys.stdin.readline().strip() if line=="": break  key,value=line.split(":")
    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)