98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征：

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1: 输入: 2 / \ 1 3 输出: true

示例 2: 输入: 5 / \ 1 4 / \ 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。

解题思路
自顶向下的思路，对于左子树左结点来说，其值小于所有祖先结点的值，对于右结点来说，其值大于所有祖先结点，那么对于任意结点，其值都有一个范围 [left,right]即 left < val < right
对于树根结点，我们可以一开始初始化 left = -INF ,right = INF
当从父结点向下时，左孩子的数值范围就变为 left < val < father ，
右孩子的数值范围就变为 father < val < right,
可以一直递归向下 要么不满足条件中途返回false回溯回到根节点，要么遍历完所有的结点返回true
代码实现

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10.  /*
  11.  LONG_MIN，LONG_MAX定义在头文件 <limits.h>中
  12.  leftmin，rightmax要定义成long型，因为如果有root->val = 1 时，和LONG_MIN比大小时，会
  13.  计算 LONG_MIN -1 ，而这个值约了int的范围导致出错
  14.  */
  15.  #include <limits.h>
  16. class Solution {
  17. public:
  18.     bool dep(TreeNode* root,long leftmin,long rightmax){
  19.          if(root == NULL)
  20.             return true;
  21.         if(root->val <= leftmin || root->val >= rightmax)
  22.             return false;
  23.         return dep(root->left,leftmin,root->val) &&  dep(root->right,root->val,rightmax);
  24.     }
  25.     bool isValidBST(TreeNode* root) {
  26.         return dep(root,LONG_MIN,LONG_MAX);
  27.     }
  28. };