芜湖市住房和城乡建设厅网站,制作的网站如何访问,微信运营推广方案,中国执行信息公开网查询题目 给定一个二叉树#xff0c;判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征#xff1a; 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 1、利用BST性质#xff1a;中序…题目 给定一个二叉树判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 1、利用BST性质中序遍历结果递增
由平衡二叉树的性质可知若是用中序遍历方法得到的结果会是递增的。 初次外如果root的结点为空或者只有1个结点的时候我们认为它也是一棵二叉搜索树。 以这样的思路写出的递归代码
/*** 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:void traversal(TreeNode* cur , vectorint vec){if(cur NULL) return;traversal(cur-left,vec);vec.push_back(cur-val);traversal(cur-right,vec);}bool isValidBST(TreeNode* root) {vectorint result;traversal(root,result);for(int i 1;iresult.size();i){if(result[i-1]result[i]) return false;//coutresult[i]endl;}return true;}
};2、不使用数组进行优化
/*** 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:TreeNode* pre NULL; //用来记录前一个结点bool isValidBST(TreeNode* root) {if(root NULL) return true;//检查左子树是否为二叉搜索树bool left isValidBST(root-left);//检查此中间结点与上一个中间结点是否是单调递增的关系if(pre ! NULL pre-val root-val) return false;pre root; //更新结点//检查右子树是否为二叉搜索树bool right isValidBST(root-right);//左子树和右子树自身必须也是二叉搜索树return left right;}
};3、回顾迭代法求解
对迭代法中序遍历稍加改动
/*** 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) {stackTreeNode* st;TreeNode* cur root;TreeNode* pre NULL;while(cur!NULL || !st.empty()){if(cur !NULL){st.push(cur);cur cur-left;}else{cur st.top();st.pop();if(pre ! NULL cur-val pre-val) return false;pre cur;cur cur-right;}}return true;}
};
