首页 > 试题广场 >

二叉搜索树判定

[编程题]二叉搜索树判定

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

输入

输出

false

示例2

输入

输出

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

算法知识视频讲解

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

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

bool isBinarySearchTree(int &pre, TreeNode *root){
    if(root==NULL)
        return true;
    if(!isBinarySearchTree(pre, root->left))
        return false;
    if(pre>=root->val)
        return false;
    else
        pre = root->val;
    if(!isBinarySearchTree(pre, root->right))
        return false;
    return true;
}

int main(){
    int n,t,v,l,r;
    cin>>n>>t;
    TreeNode *T = (TreeNode*)malloc(sizeof(TreeNode)*(n+1));
    TreeNode *R = &T[t];
    for(int i=1;i<=n;i++){
        cin>>v>>l>>r;
        T[i].val = v;
        T[i].left = l?&T[l]:0;
        T[i].right = r?&T[r]:0;
    }
    int pre = -1;
    cout<<(isBinarySearchTree(pre,R)?"true":"false")<<endl;
    return 0;
}

发表于 2019-09-15 09:04:20 回复(0)

Python

康斯坦奇

Python版本的case：73.33%，AC不了，不知道为啥？

class TreeNode:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None
class Solution:
    def isBinarySearchTree(self,root):
        if root == None:
            return True
        result = self.midOrder(root)
        for i in range(len(result)):
            if i == len(result)-1:
                break
            if result[i] > result[i+1]:
                return False
        return True
    def midOrder(self,root):
        if root == None:
            return []
        return self.midOrder(root.left) + [root.val] + self.midOrder(root.right)
    def createTree(self,line,i):
        if i < 0:
            return None
        a,b,c = line[i]
        root = TreeNode(a)
        root.left = self.createTree(line,b-1)
        root.right = self.createTree(line,c-1)
        return root
s = Solution()
input1 = [int(x) for x in input().split()]
array = []
for i in range(input1[0]):
    input2 = [int(x) for x in input().split()]
    array.append(input2)
root= s.createTree(array,input1[1] - 1)
print('true' if s.isBinarySearchTree(root) else 'false')

发表于 2019-08-21 12:54:13 回复(2)

不是很黑

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int shu[100000],i;
void In(TreeNode* t){
	if(t->left) In(t->left);
	shu[i++]=t->val;
	if(t->right) In(t->right);
}
bool isBinarySearchTree(int n, TreeNode * root) {
	In(root);
	for(int i=0;i<n-1;i++){
		if(shu[i]>shu[i+1])
		return false;
	}
	return true;
}

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

发表于 2020-04-10 14:40:47 回复(0)

PandaLai

运行时间：45ms

占用内存：7164k

思路：直接先序遍历整棵树，访问结点时检查该结点的值是否合理（在以root为根的二叉搜索树中，左子树结点的值必须小于root的值，而右子树结点的值必须大于root的值），递归时将结点值的上界和下界作为参数传递。

#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 dfs(TreeNode * root, int upper_bound, int lower_bound) {
    if(!root)    return true;
    return root->val > lower_bound && root->val < upper_bound && dfs(root->left, root->val, lower_bound) && dfs(root->right, upper_bound, root->val);
}

bool isBinarySearchTree(int n, TreeNode * root) {
    // do something !
    return dfs(root, INT_MAX, INT_MIN);
}

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

发表于 2020-04-10 13:03:47 回复(0)

ppdbz

卡了86.67%，估计是速度不行，有没有用Python的大佬优化一下
def serch_tree():
    n, r = [int(x) for x in input().split(' ')]
    tree_array = [[int(x) for x in input().split(' ')] for j in range(n)]
    if r == None:
        return 'false'
    for i in range(n):
        N0 = tree_array[i]
        if N0[1] != 0:
            if tree_array[N0[1]-1][0]>=N0[0]:
                return 'false'
        if N0[2] != 0:
            if tree_array[N0[2]-1][0]<=N0[0]:
                return 'false'
    return 'true'
a = serch_tree()        
print(a)

发表于 2020-03-10 10:04:10 回复(0)

freezerhan

#include <stdio.h>
#include <algorithm>

using namespace std;

int G[100003][2];
int val[100003];
bool ret;

pair<int,int> dfs(int u) {
	pair<int,int> foo, bar;
	if (G[u][0] == 0) {
		foo = {val[u], val[u] - 1};
	} else {
		foo = dfs(G[u][0]);
	}
	if (G[u][1] == 0) {
		bar = {val[u] + 1, val[u]};
	} else {
		bar = dfs(G[u][1]);
	}

	if (foo.second >= val[u] || bar.first <= val[u]) {
		ret = false;
	}
	return {foo.first, bar.second};
}

int main() {
	ret = true;
	int n, root;
	scanf("%d %d", &n, &root);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &val[i]);
		scanf("%d %d", &G[i][0], &G[i][1]);
	}
	dfs(root);
	puts(ret ? "true" : "false");
	return 0;
}

发表于 2019-11-23 11:05:23 回复(0)

C/C++

ElonB

/*
考察中序遍历
*/
#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 &prev, TreeNode * root)
{
    if(root == NULL) return true;
    if(!isBinarySearchTree(prev, root->left)) return false;
    if(prev >= root->val) return false; //判断是否满足二叉搜索树(从小到大)
    prev = root->val; //进入中序遍历下一个节点前，更新prev
    if(!isBinarySearchTree(prev, root->right)) return false;
    return true;
}

int main(void)
{
    //freopen("input.txt", "r", stdin);
    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;
    }
    int prev = INT_MIN; //记录中序遍历的前一个节点的val
    printf(isBinarySearchTree(prev, root) ? "true\n" : "false\n");
    return 0;
}

编辑于 2019-07-17 19:29:39 回复(1)

哟，我喜欢


	bool check(TreeNode* root, int& prev){



	    if(root==NULL)



	        return true;



	    if(!check(root->left,prev))



	        return false;



	    if(root->val<=prev)



	        return false;



	    else



	        prev = root->val;



	    return check(root->right,prev);



	}

发表于 2019-06-17 12:00:38 回复(0)

Java

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)

pein531

先重建二叉树，再判断中序遍历的序列是否是递增的，不过中序遍历需要迭代实现，递归实现会栈溢出。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;

class TreeNode {
    public int val;             // 本结点value
    public int leftId = 0;      // 左孩子的节点编号
    public int rightId = 0;     // 右孩子的节点编号
    TreeNode left, right;       // 左右孩子节点引用
    public TreeNode(int val, int leftId, int rightId){
        this.val = val;
        this.leftId = leftId;
        this.rightId = rightId;
        left = null;
        right = null;
    }
}

public class Main {
    static TreeNode[] nodes;
    static ArrayList<Integer> inorderSeq;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]), root = Integer.parseInt(params[1]);
        nodes = new TreeNode[n + 1];
        for(int i = 1; i <= n; i++) {
            params = br.readLine().trim().split(" ");
            int val = Integer.parseInt(params[0]);
            int leftId = Integer.parseInt(params[1]);
            int rightId = Integer.parseInt(params[2]);
            TreeNode node = new TreeNode(val, leftId, rightId);
            nodes[i] = node;
        }
        // 重建二叉树
        TreeNode tree = nodes[root];
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(tree);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.leftId != 0) {
                node.left = nodes[node.leftId];       // 找到左孩子
                queue.offer(node.left);
            }
            if(node.rightId != 0) {
                node.right = nodes[node.rightId];     // 找到右孩子
                queue.offer(node.right);
            }
        }
        // 通过中序遍历来验证是否是二叉搜索树
        inorderSeq = inorder(tree);
        boolean res = true;
        for(int i = 1; i < inorderSeq.size(); i++){
            if(inorderSeq.get(i) <= inorderSeq.get(i - 1)){
                res = false;     // 中序遍历序列不是递增的
                break;
            }
        }
        System.out.println(res);
    }
    
    public static ArrayList<Integer> inorder(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null) return res;
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()){
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

发表于 2021-04-13 11:24:55 回复(0)

牛客196781578号

#include <cstdlib>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct Node{
    int left;
    int right;
    int val;
    Node(int x): val(x), left(0), right(0) {}
};


int main() {
    Node* one = new Node(0);
    vector<Node* >trees(100005, one);
    int length, root;
    cin >> length >> root;
    for(int i = 1;i <= length;i++){
        int val_i, left_i, right_i;
        cin >> val_i >> left_i >> right_i;
        Node* root = new Node(val_i);
        root->left = left_i;
        root->right = right_i;
        trees[i] = root;
    }

    stack<int> s;
    int cur = root; // 根节点
    bool flag = true;
    bool start = true;
    int pre;
    while(cur > 0 || !s.empty()){
        // cout << cur << endl;
        if(cur > 0){
            s.push(cur);
            cur = trees[cur]->left;
        }else{
            cur = s.top();
            s.pop();
            // cout << cur << endl;
            if(start){
                start = false;
            }else{
                if(trees[cur]->val < pre){
                    flag = false;
                    break;
                }
            }
            pre = trees[cur]->val;
            cur = trees[cur]->right;
        }   
    }
    if(!flag){
        cout << "false" << endl;
    }else{
        cout << "true" << endl;
    }
}
// 64 位输出请用 printf("%lld")

发表于 2024-03-19 17:43:22 回复(0)

牛客129983867号

#用中序遍历 递归只能过73.33% 递归次数太多，导致堆栈溢出
#定义树节点
class TreeNode(object):
    def __init__(self,value,left=None,right=None):
        self.value = value
        self.left = left
        self.right = right
class Tree(object):
    def __init__(self,input_dict,root:int):
        for i in range(1,len(input_dict)+1):
            new_node = TreeNode(input_dict[i][0],input_dict[i][1],input_dict[i][2])
            input_dict[i]=new_node
        for i in range(1,len(input_dict)+1):
            
            if input_dict[i].left!=0:
                input_dict[i].left = input_dict[input_dict[i].left]
            else:
                input_dict[i].left=None

            if input_dict[i].right!=0:
                input_dict[i].right = input_dict[input_dict[i].right]
            else:
                input_dict[i].right=None
        self.root = input_dict[root]
    def _is_valid(self,root):
 
        if root:#不为空
            left_result = self._is_valid(root.left)
            right_result = self._is_valid(root.right)
            if left_result and right_result:
                if root.left and root.left.value< root.value and not root.right:#有左节点,无右节点
                    return True
                if root.right and root.right.value > root.value and not root.left:#有右节点,无左节点
                    return True
                if root.right and root.right.value > root.value and root.left and root.left.value< root.value:#有右节点,左节点
                    return True
                if not root.right and not root.right:#叶子节点直接返回True
                    return True
                return False #都不满足返回false
            else:
                return False 
        else:
            return True
                    

#处理输入

while True:
    try:
        n, root = map(int, input().split(" "))
        input_dict = {}
        for i in range(1,n+1):
            input_dict[i]=list(map(int,input().split(" ")))
        #构建树
        tree = Tree(input_dict,root)
        result = tree._is_valid(tree.root)
        if result:
            print("true")
        else:
            print("false")
    except:
        break

发表于 2021-04-12 20:45:10 回复(0)

上安

import javax.imageio.stream.ImageInputStream;
import java.util.Scanner;
import java.util.*;

import static java.lang.Integer.MAX_VALUE;

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

        }
    }
    long  pre= Long.MIN_VALUE;
    boolean isBinarySearchTree(TreeNode root){
        //用中序遍历 递归只能过73.33% 递归次数太多，导致堆栈溢出
        if(root == null){ return true;}
        if(!isBinarySearchTree(root.left)){
            return false;
        }else if(root.val<=pre){
            return false;
        }else{
            pre = root.val;
            return isBinarySearchTree(root.right);
        }

    }
    boolean isBinarySearchTree2(TreeNode root){
        if(root == null){ return true;}
        //用栈迭代
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp = root;
        long pre = Long.MIN_VALUE;

        while(!stack.isEmpty()||temp!=null){
            //1.先将根节点入栈
            //2.将所有左孩子入栈
            while(temp!=null){
                stack.push(temp);
                temp = temp.left;
            }
            //3.访问栈顶
            temp=stack.pop();
            if(temp.val<=pre){
                return false;
            }else{
                pre = temp.val;
               // 4.如果发现栈顶存在右孩子
                if(temp.right!=null){
                      temp =temp.right;
                }else{
                    temp = null;
                }
            }
        }
        return true;


    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        TreeNode[ ] TreeNodes = new TreeNode[n+1];
        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()];
        }
        boolean flag = new Main().isBinarySearchTree2(TreeNodes[m]);
        System.out.println(flag);

    }
}

发表于 2020-06-17 10:04:47 回复(0)

louis_ncu

//占用的内存有点高了
//时间：50ms
//内存：5500KB
#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(TreeNode * root, int leftVal, int rightVal) {
// do something !
    if(root == NULL) {
        return true;
    }
    else{
        if(root->val <= leftVal || root->val >= rightVal) {
            return false;
        }
        return isBinarySearchTree(root->left, leftVal, root->val) 
            && isBinarySearchTree(root->right, root->val, rightVal);
    }
}

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(root, INT_MIN, INT_MAX)?"true\n":"false\n");
    return 0;
}

发表于 2020-05-17 22:08:19 回复(0)

Mmao丶

class Solution(object):
    def __init__(self, tree_lst, root_idx):
        self.tree_lst = [0] + tree_lst
        self.root_idx = root_idx
        self.tmp = float('-inf')
    
    def inorder(self, node_idx):
        if not node_idx:
            return True
        if not self.inorder(self.tree_lst[node_idx][1]):
            return False
        if self.tmp > self.tree_lst[node_idx][0]:
            return False
        else:
            self.tmp = self.tree_lst[node_idx][0]
        if not self.inorder(self.tree_lst[node_idx][2]):
            return False
        return True
        
    def check(self):
        return 'true' if self.inorder(self.root_idx) else 'false'


if __name__ == '__main__':
    n, root_idx = map(int, raw_input().strip().split())
    tree_lst =[list(map(int, raw_input().strip().split())) for _ in xrange(n)]
    print(Solution(tree_lst, root_idx).check())

73.33% 思路和排行榜上c++一样，为何过不了。。

class Solution(object):
    def __init__(self, tree_lst, root_idx):
        self.tree_lst = [0] + tree_lst
        self.root_idx = root_idx
        self.tmp = float('-inf')
    
    def inorder(self):
        stack, cur = [], self.root_idx
        while stack&nbs***bsp;cur:
            while cur:
                stack.append(cur)
                cur = self.tree_lst[cur][1]
            while stack:
                node_idx = stack.pop()
                if self.tmp > self.tree_lst[node_idx][0]:
                    return 'false'
                else:
                    self.tmp = self.tree_lst[node_idx][0]
                if self.tree_lst[node_idx][2]:
                    cur = self.tree_lst[node_idx][2]
                    break
        return 'true'


if __name__ == '__main__':
    n, root_idx = map(int, raw_input().strip().split())
    tree_lst =[list(map(int, raw_input().strip().split())) for _ in xrange(n)]
    print(Solution(tree_lst, root_idx).inorder())

参考java的一个答案，用栈迭代过了。。。python递归真是个弟弟。。。

编辑于 2020-03-20 22:43:12 回复(1)

gywy

参考了大佬们的代码，终于写出来了，按照中序遍历的顺序，如果当前节点的数值小于前驱节点的数值，那么就不是二叉搜索树。

#include <cstdio>

using namespace std;

const int N = 100010;

struct Node
{
    int l, r, v;
}tr[N];
int n, root;

bool dfs(int u)
{  
    static int prev = 0;

    if (u)
    {
        if (!dfs(tr[u].l)) return false;

        if (prev && tr[u].v < tr[prev].v) return false;

        prev = u;

        if (!dfs(tr[u].r)) return false;
    }
    return true;


}

int main()
{
    scanf("%d%d", &n, &root);
    int v, l, r;
    for (int i = 1; i <= n; i ++)
    {
        scanf("%d%d%d", &v, &l, &r);
        tr[i] = {l, r, v};
    }
    if (dfs(root)) puts("true");
    else puts("false");

    return 0;
}

发表于 2020-03-18 08:50:24 回复(0)

皮蛋秀柚秋

卡在86.67%，咋回事

#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(TreeNode * root) {
   if(!root) return true;
   else if(!root->left&&!root->right) return true;
   else if(root->left&&root->right)
   {
       if(root->left->val>=root->val||root->right->val<=root->val)
           return false;
       else return isBinarySearchTree(root->left)&&isBinarySearchTree(root->right);
   }
   else if(root->left)
   {
       if(root->left->val>=root->val) return false;
       return isBinarySearchTree(root->left);
   }
   else {
       if(root->right->val<=root->val) return false;
       return isBinarySearchTree(root->right);
           
   }
}

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(root)?"true\n":"false\n");
return 0;
}

参考了大佬们的思路，要这样才行。。

#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(TreeNode * root) {
   if(!root) return true;
   else if(!root->left&&!root->right) return true;
   else if(root->left&&root->right)
   {
       if(root->left->val>=root->val||root->right->val<=root->val)
           return false;
       else return isBinarySearchTree(root->left)&&isBinarySearchTree(root->right);
   }
   else if(root->left)
   {
       if(root->left->val>=root->val) return false;
       return isBinarySearchTree(root->left);
   }
   else {
       if(root->right->val<=root->val) return false;
       return isBinarySearchTree(root->right);
           
   }
}
*/
bool solve(int& pre,TreeNode* root)
{
    if(!root) return true;
    if(!solve(pre,root->left)) return false;
    if(pre>=root->val) return false;
    pre = root->val;
    if(!solve(pre,root->right)) return false;
    return true;
}
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(root)?"true\n":"false\n");
int pre = -1;
if(solve(pre,root))
    cout<<"true"<<endl;
else cout<<"false"<<endl;
return 0;
}

编辑于 2019-09-21 21:44:58 回复(1)

theflood

卡86.67%, 一个超长的测试用例，本以为是出现了回环，加入reach之后还是过不去。求大神看看什么情况。

#include <iostream>
#include <istream>
#include <vector>

using namespace std;

struct node{
    long val;
    long left;
    long right;
};

bool dfs(vector<node>& Nodes, vector<int>& reach, long root){
    long left = Nodes[root].left;
    long right = Nodes[root].right;
    bool flag = true;
    if(left == 0 && right == 0) return true;
    if(left != 0){
        if(reach[left] == 0) {
            reach[left] = 1;
        } else{
            return false;
        }
        if(Nodes[left].val >= Nodes[root].val) return false;
        else flag &= dfs(Nodes, reach, left);
    }
    if(right != 0){
        if(reach[right] == 0){
            reach[right] = 1;
        } else{
            return false;
        }
        if(Nodes[right].val <= Nodes[root].val) return false;
        else flag &= dfs(Nodes, reach, right);
    }
    return flag;
}

int main(){
    
    long n, start;
    cin >> n >> start;
    vector<node> Nodes(n+1);
    vector<int> reach(n+1, 0); 
    
    for(long i = 1; i<=n; i++){
        cin >> Nodes[i].val >> Nodes[i].left >> Nodes[i].right;
    }
    
    if(dfs(Nodes, reach, start)){
        cout << "true" << endl;
    } else{
        cout << "false" << endl; 
    }
    
    return 0;
}

发表于 2019-09-12 20:34:19 回复(1)

拉丝针德绣

#include <iostream>
#include <stack>

using namespace std;

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

static inline void get_left_nodes(TreeNode *root, stack<TreeNode *>& q)
{
    TreeNode *node = root;
    while (node) {
        q.push(node);
        node = node->left;
    }
}

static bool valid_bst(TreeNode *root)
{
    if (!root)
        return true;
        
    stack<TreeNode *> st;
    get_left_nodes(root, st);

    bool visited = false;
    int minv;
    while (!st.empty()) {
        TreeNode *node = st.top();
        st.pop();
        if (visited && node->val <= minv)
            return false;
        visited = true;
        minv = node->val;
        get_left_nodes(node->right, st);
    }
    
    return true;
}

int main()
{
    int n, root;
    cin >> n >> root;
    TreeNode *tree = (TreeNode *)malloc((n + 1) * sizeof(TreeNode));
    
    int val, l, r;
    for (int i = 1; i <= n; ++i) {
        cin >> val >> l >> r;
        tree[i].val = val;
        tree[i].left = l ? &tree[l] : NULL;
        tree[i].right = r ? &tree[r] : NULL;
    }
    
    if (valid_bst(&tree[root]))
        cout << "true\n";
    else
        cout << "false\n";
    
    free(tree);
    return 0;
}

发表于 2019-08-17 19:23:01 回复(0)

微凉下午茶

思路是：根据节点信息还原成二叉树，再中序遍历该树，判断遍历结果是否是严格递增的。如果是，打印‘true’；否则，打印‘false’，但是代码

总是70%的case，请大神指正。

class TreeNode:                     # 定义树的节点结构
    def __init__(self,item):
        self.val = item
        self.left = None
        self.right = None

class Tree(object):
    def __init__(self):
        self.root = None

    def addNode(self,lines,i):   # 还原二叉树，lines是除却第0行之外的所有节点信息，是一个n*3的矩阵
        if i < 0:         # i是该节点的下一个子节点的在lines里的横坐标，它表示该节点下的子节点信息在lines矩阵的第几行
            return None
        a,b,c = lines[i]
        new_node = TreeNode(a)
        new_node.left = self.addNode(lines,b-1)   # 这里注意坐标要减1，因为lines矩阵抛除了输入的第0行，是从输入的第1行开始的
        new_node.right = self.addNode(lines,c-1)
        return new_node

    def inorder_travel_nre(self,node,l):      # 中序遍历该树
        stack = []
        pos = node
        while pos or stack:
            if pos:
                stack.append(pos)
                pos = pos.left
            else:
                pos = stack.pop()
                if pos.val:
                    l.append(pos.val)
                pos = pos.right

tree = Tree()
node_num, root_index =  map(int,input().split())  # 接收第0行输入，node_num表示该树共几个节点，root_index表示该树的根节点是在第几行

if node_num == 1:  # 如果该树只有一个节点，又由题意知，该树是合法的树，因此该树一定是搜索树
    print('true')
else:              # 如果该树有多个节点
    lines = []     # lines是除去第0行输入的节点信息，他是从输入的第1行开始的n*3矩阵
    while node_num >0:
        lines.append(list(map(int,input().split())))
        node_num -= 1

    tree.root = tree.addNode(lines,root_index-1)  # 还原二叉树

    tmpl = []                                     # 保存中序遍历结果
    tree.inorder_travel_nre(tree.root,tmpl)
    is_flag = 'true'

    for y in range(1,len(tmpl)):                  # 判断遍历结果是否严格递增
        if tmpl[y] <= tmpl[y-1]:
            is_flag = 'false'
            break
    print(is_flag)

发表于 2019-08-06 08:35:22 回复(1)

提交观点

问题信息

C++工程师 Momenta 树 2019 Java工程师递归

来自：Momenta2019...

上传者：小小

难度：

20条回答 43收藏 5954浏览

通过挑战的用户

查看代码

牛牛耶

2023-02-06 17:22:27
绝望的CPP

2022-09-08 16:23:58
牛客49937...

2022-09-03 17:02:05
前端学习中

2022-08-26 11:11:33
荣耀9527号

2022-08-25 09:44:33

二叉搜索树判定

输入描述:

输出描述:

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题