首页 > 试题广场 > 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

2个回答

添加回答
#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.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)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号