首页 > 试题广场 >

二叉搜索树判定

[编程题]二叉搜索树判定
  • 热度指数：2304 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
例如：
输入：
    5
   / \
  1   3
     / \
    4   6
输出: false
二叉树节点定义如下，如果使用其他语言，其二叉树节点定义类似：
/**
 * C++
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 
# Python
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
/**
 * Go
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

输入描述:
第一行两个数n,root，分别表示二叉树有n个节点，第root个节点时二叉树的根
接下来共n行，第i行三个数val_i,left_i,right_i，分别表示第i个节点的值val是val_i,左儿子left是第left_i个节点，右儿子right是第right_i个节点。
节点0表示空。
1<=n<=100000,保证是合法的二叉树


输出描述:
输出"true"如果给定二叉树是二叉搜索树，否则输出"false"
示例1

输入

5 1
5 2 3
1 0 0
3 4 5
4 0 0
6 0 0

输出

false
示例2

输入

5 1
2 2 3
1 0 0
4 4 5
3 0 0
6 0 0

输出

true

备注:
你可以使用以下C++代码作为模板，实现其中的isBinarySearchTree()函数。对于其它语言可类似的实现。

#include <bits/stdc++.h>

using namespace std;

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

bool isBinarySearchTree(int n, TreeNode * root) {
// do something !

}

int main(void) {
int n,r;
scanf("%d%d",&n,&r);
TreeNode * tree, * root;
tree = (TreeNode*)malloc(sizeof(TreeNode)*(n+1));
root = &tree[r];
for (int i=1;i<=n;i++) {
int v,l,r;
scanf("%d%d%d",&v,&l,&r);
tree[i].val = v;
tree[i].left = l?&tree[l]:0;
tree[i].right = r?&tree[r]:0;
}
printf(isBinarySearchTree(n,root)?"true\n":"false\n");
return 0;
}
算法知识视频讲解
添加回答
Java
在备战秋招的突尼斯海怪很爱看剧头像 在备战秋招的突尼斯海怪很爱看剧
importjava.util.*;
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
publicclassMain {
    publicstaticvoidmain(String[] args) {
        Scanner in = newScanner(System.in);
        intn = in.nextInt(), r = in.nextInt();
        inta[][] = newint[n + 1][5];
        for(inti = 1; i <= n; i++) {
            a[i][0] = in.nextInt();
            a[i][3] = in.nextInt();
            a[i][4] = in.nextInt();
        }
        Queue<Integer>s = newLinkedList<>();
        s.add(r);
        while(s.size() > 0) {
            introot = s.poll();
            if(a[root][3] != 0) {
                if(a[a[root][3]][0] < a[root][0]) {
                    a[a[root][3]][2] = a[root][0];
                    if(a[root][1] != 0) {
                        if(a[a[root][3]][0] > a[root][1]) {
                            a[a[root][3]][1] = a[root][1];
                        } else{
                            System.out.print(false);
                            return;
                        }
                    }
                    s.add(a[root][3]);
                } else{
                    System.out.print(false);
                    return;
                }
            }
            if(a[root][4] != 0) {
                if(a[a[root][4]][0] > a[root][0]) {
                    a[a[root][4]][1] = a[root][0];
                    if(a[root][2] != 0) {
                        if(a[a[root][4]][0] < a[root][2]) {
                            a[a[root][4]][2] = a[root][2];
                        } else{
                            System.out.print(false);
                            return;
                        }
                    }
                    s.add(a[root][4]);
                } else{
                    System.out.print(false);
                    return;
                }
            }
        }
        System.out.print(true);
    }
}
发表于 2024-10-28 14:19:35 回复(0)
Java
Stephenz0927头像 Stephenz0927
采用java编写，估计是导入二叉树的过程中有哪些问题，一直不能AC只能过73.3%，试过中序，栈，还有大小值遍历都不能AC，希望大佬可以指点一下。 
import java.util.*;
import static java.lang.Long.*;
public class Main{
    long pre = Long.MIN_VALUE;
    public static void main(String[] agrs){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        TreeNode[] TreeNodes = new TreeNode[n+1];
        TreeNodes[0] = null;
        for (int i = 1 ; i <= n; i++){
            TreeNodes[i] = new TreeNode(0);
        }
        for(int i = 1;i <= n ; i++){
            TreeNodes[i].val = in.nextInt();
            TreeNodes[i].left = TreeNodes[in.nextInt()];
            TreeNodes[i].right = TreeNodes[in.nextInt()];
        }
        if(new Main().isBinarySearchTree(TreeNodes[m])){
            System.out.println("true");
        }else{
            System.out.println("false");
        }
    }


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

    public boolean isBinarySearchTree(TreeNode root){
            if(root==null){
                return true;
            }
            if(!isBinarySearchTree(root.left)){
                return false;
            }
            if(root.val <= pre){
                return false;
            }
            pre = root.val;    
            return isBinarySearchTree(root.right); 
    }
}

发表于 2020-05-08 00:42:59 回复(6)
提交观点

问题信息

C++工程师 Momenta 树 2019 Java工程师 递归
来自：Momenta2019...
上传者：小小
难度：
2条回答 6597浏览

热门推荐

通过挑战的用户

查看代码

相关试题

二叉搜索树判定

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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