二叉搜索树判定

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

热度指数：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

输入

输出

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