给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 例如： 输入： 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"

备注:

你可以使用以下C++代码作为模板，实现其中的isBinarySearchTree()函数。对于其它语言可类似的实现。#include 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;iint 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;}