首页 > 试题广场 > BST判定
[编程题]BST判定

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

对任何非叶子节点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

输出

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;
    }
} 
编辑于 2019-01-16 10:35:50 回复(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;
}


发表于 2019-01-11 20:13:13 回复(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;
    }

}
发表于 2019-05-28 09:58:31 回复(0)
估计我写的太复杂了
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)

发表于 2019-04-27 21:12:15 回复(0)