列表

详情

MMT12. 二叉搜索树判定

描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
例如：
输入：
    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++ 解法, 执行用时: 25ms, 内存消耗: 6676KB, 提交时间: 2020-07-24 

#include <bits/stdc++.h>
    using namespace std;
    struct Node
    {
        int val;
        int left;
        int right;    
    };
    int n,root;
    vector<Node> vv;
    vector<int> ans;
    void inorder(int r)
    {
        if(!r)
            return;
        inorder(vv[r].left);
        ans.push_back(vv[r].val);
        inorder(vv[r].right);
    }
    bool check()
    {
        int pre = -0x7fffffff;
        for(int i = 0; i < ans.size(); ++i)
        {
            if(ans[i] <= pre)
                return false;
            pre = ans[i];
        }
        return true;
    }
    int main(void)
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>n>>root;
        vv.resize(n+1);
        int v,l,r;
        for(int i = 1; i <= n; ++i)
            cin>>vv[i].val>>vv[i].left>>vv[i].right;
        inorder(root);
        if(check())
            cout << "true" << endl;
        else
            cout << "false" << endl;
    }

C++ 解法, 执行用时: 26ms, 内存消耗: 5800KB, 提交时间: 2021-09-09 

#include <bits/stdc++.h>

using namespace std;

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


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

C++ 解法, 执行用时: 26ms, 内存消耗: 7472KB, 提交时间: 2021-09-16 

#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 min, int max) {
    if (root == NULL) return true;

    bool self = root->val <= max && root->val >= min;

    bool left = isBinarySearchTree(root->left, min, root->val);
    bool right = isBinarySearchTree(root->right, root->val, max);

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

C++ 解法, 执行用时: 30ms, 内存消耗: 7380KB, 提交时间: 2020-10-31 

#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 min,int max) {
    if(root==NULL) return true;
    
    bool self = root->val<=max && root->val>=min;
    
    bool left = isBinarySearchTree(root->left,min,root->val);
    bool right = isBinarySearchTree(root->right,root->val,max);
    
    return self && left && 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,INT_MIN,INT_MAX)?"true\n":"false\n");
return 0;
}

C++ 解法, 执行用时: 30ms, 内存消耗: 7416KB, 提交时间: 2020-11-01 

#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 min,int max) {
    if(root==NULL) return true;
    
    bool self = root->val<=max && root->val>=min;
    
    bool left = isBinarySearchTree(root->left,min,root->val);
    bool right = isBinarySearchTree(root->right,root->val,max);
    
    return self && left && 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,INT_MIN,INT_MAX)?"true\n":"false\n");
return 0;
}

上一题

© 2024 nowcoder.com