(BST 递归) leetcode98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less thanthe node's key.The right subtree of a node contains only nodes with keys greater than the node's key.Both the left and right subtrees must also be binary search trees.

Example 1:

Input: 2 / \ 1 3 Output: true

Example 2:

5 / \ 1 4   / \   3 6 Output: false Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value   is 5 but its right child's value is 4.-----------------------------------------------------------------------------------------这个是一个Binary Search Tree的问题，即二叉搜索树。参考大佬的博客：http://www.cnblogs.com/grandyang/p/4298435.html第一个解法：这个题实际上是简化了难度，因为这个题说的BST指的是左 < 根 < 右，而不是 左 <= 根 < 右，这样的话就可以方便的使用中序遍历将所有值的节点保存到一个数组里，然后遍历这个数组，判断数组里面是否为升序（即a < b，不是 a <= b），然后返回false和true。左 <= 根 < 右这个情况中 10 10 / 和 \ 中，10 10 用中序遍历最后得到的数组都是[10,10],[10,10]，但是左边的是BST，而右边却不是BST，不好区分，如果去掉等号的话，就可以认为都不是BST，难度下降了不少。 C++代码： /** * 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) return true; vector<int> vec; inorder(root,vec); for(int i = 0; i < vec.size() - 1; i++){ if(vec[i+1] <= vec[i]) return false; } return true; } void inorder(TreeNode *root,vector<int> &vec){ if(!root) return; inorder(root->left,vec); vec.push_back(root->val); inorder(root->right,vec); } };

第二个解法：

根据Grandyang大佬的解法中，这个题可以用本身的性质来做，这个BST就是左 < 根 <  右，所以利用递归来判断是否满足这个条件。可以设置最小值和最大值。

C++代码：

using ll = long long; // C++11里面的特性。 /** * 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) { return valid(root,LONG_MIN,LONG_MAX); } bool valid(TreeNode *root,ll mmin,ll mmax){ if(!root) return true; if(root->val <= mmin || root->val >= mmax) return false; return valid(root->left,mmin,root->val) && valid(root->right,root->val,mmax); } };

 

转载于:https://www.cnblogs.com/Weixu-Liu/p/10774835.html