LeetCode 98. Validate Binary Search Tree( 递归,BST )

题意:判断一个二叉树是否为 二叉搜索树BST

题解:所有思路都是去找二叉树中不满足BST性质的节点,找到了,就不符合,找不到就符合。那么怎么去找呢?我提供两种思想。

第一个是,BST的中序遍历是一个有序数组,所以把BST 中序遍历的结果拿出来,看看是不是有序的就可以了。很简单。那如果不让你用额外的空间呢?那就在中序遍历的过程中,判断是不是有序。我们维护一个值last,这个值是遍历数组的前一个元素,如果发现有当前元素小于前一个元素,就是false

第二个思路是,判断每个节点是否符合区间。这种方法随便哪种遍历都可以。根节点的区间,是没有限制的,Int.Min ~ Int.Max。那么左子节点就是Int.Min ~ root->val ,那么左子节点的右子节点,就是root->left->val,root->val。综上所述,每遍历到一个节点时,它的区间的最小值或者最大值都要变成它父亲节点的值,这取决于左子树还是右子树。

这道题目的坑点是,数据范围是 -(1<<31) ~ (1<<31)-1 ,就是int的边界值。

解法一:

 int father = -1*(1<<31);      int tag=-1;      bool isValidBST(TreeNode* root) {          if(root==NULL)              return true;          if(isValidBST(root->left))          {              if(root->val>father||(tag==-1&&root->val==father))              {                  father = root->val;                  tag=1;                  return isValidBST(root->right);              }          }          return false;      }

第二种

/**   * Definition for a binary tree node.   * struct TreeNode {   *     int val;   *     TreeNode *left;   *     TreeNode *right;   *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}   * };   */  class Solution {  public:        bool isValidBST(TreeNode* root) {            if(root==NULL)              return true;         return fun(root,NULL,NULL);        }        bool fun(TreeNode* root,TreeNode* min,TreeNode* max)      {            if(root->left!=NULL)          {            if(!fun(root->left,min,root))              return false;          }            if(root->right!=NULL)          {            if(!fun(root->right,root,max))              return false;          }            if(((min!=NULL&&root->val>min->val)||(min==NULL)) &&(             (max!=NULL&&root->val<max->val )||(max==NULL)))              return true;          else              return false;          }    };