BST判定

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

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

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
}

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

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

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

}