LeetCode树——验证二叉搜索树（C++）

题目描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/validate-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

题目中已经给出说明，有效的二叉搜索树左子树<根<右子树，因此，二叉搜索树的中序遍历序列是递增序列，因此，可以在进行中序遍历的时候将遍历到的元素与上一个元素对比，若上一个元素大于等于该元素，则该二叉搜索树的中序遍历序列不满足递增，因此，该二叉搜索树不是有效的。代码如下：

/** * 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; stack<TreeNode*>s; stack<int>m;//用来存储中序遍历的输出 TreeNode* tem = root; s.push(tem); while(!s.empty()){ while(tem->left != NULL){ tem = tem->left; s.push(tem); } while(!s.empty()){ tem = s.top(); if(!m.empty()){//当中序遍历序列非空时 if(m.top()>=(tem->val))//若前一个元素大于等于该元素，则直接返回false return false; else{ m.push(tem->val);//若满足递增条件，则直接存入栈中 } } else{ m.push(tem->val); } s.pop(); if(tem->right != NULL){ tem = tem->right; s.push(tem); break; } } } return true//若顺利执行到此处，说明中序遍历序列满足递增，该二叉搜索树有效 }

来看一下跑的效果怎么样： 这个空间复杂度也太高了，呜呜呜，再修改一下。考虑到没必要存储全部的中序遍历序列，因此只保留上一个的数值即可，修改如下:

/** * 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; stack<TreeNode*>s; int last;//添加 int flag=0;//添加 TreeNode* tem = root; s.push(tem); while(!s.empty()){ while(tem->left != NULL){ tem = tem->left; s.push(tem); } while(!s.empty()){ tem = s.top(); if(flag){//判断 if(last>=tem->val){ return false; } else{ last=tem->val; } } else{//判断 flag++; last = tem->val; } s.pop(); if(tem->right != NULL){ tem = tem->right; s.push(tem); break; } } } return true; } };

但是，运行时间又增加了。。。