题目描述
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
复制代码
- 输入:root = [2,1,3]
- 输出:true
示例 2:
复制代码
- 输入:root = [5,1,4,null,null,3,6]
- 输出:false
- 解释:根节点的值是 5 ,但是右子节点的值是 4 。
个人C++解答
GYL
利用二叉搜索树的定义,中序遍历为升序这样的条件去判断,起初用递归按照条件来写,但是由于没考虑左右字数必须都是二叉搜索树也就是说不能只小于或大于根节点这一个条件,所以没做出来
复制代码
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode() : val(0), left(nullptr), right(nullptr) {}
- * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
- * right(right) {}
- * };
- */
- class Solution {
- vector<long> vec;
- public:
- bool isValidBST(TreeNode* root) {
- inOrder(root);
- for (int i = 1; i < vec.size(); i++) {
- if (vec[i] - vec[i - 1] <= 0) {
- return false;
- }
- }
- return true;
- }
- void inOrder(TreeNode* root) {
- if(root == nullptr) return;
- inOrder(root->left);
- vec.push_back(root->val);
- inOrder(root->right);
- }
- };