BST判定

[编程题]BST判定

热度指数：839 时间限制：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

输出

算法知识视频讲解

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)