赞
踩
二叉搜索树操作。继续。
记录 五十四【98.验证二叉搜索树】
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3]
输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。
提示:
树中节点数目范围在[1, 104] 内
-2^31 <= Node.val <= 2^31 - 1
正确思路:对一个二叉搜索树中序遍历,可以得到有序递增数列。这是二叉搜索树特性,也是验证是否是二叉搜索树的方式。
递归法:递归法实现三种方式:
第一种:定义一个数组,在中序遍历过程中搜集数值;再对数组遍历,判断是否递增。代码实现:
/** * 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 { public: void traversal(TreeNode* cur,vector<int>& vec) { if(!cur) return;//终止条件叶子节点 traversal(cur->left,vec); vec.push_back(cur->val); traversal(cur->right,vec); return; } bool isValidBST(TreeNode* root) { vector<int> vec; traversal(root,vec); for(int i = 1;i < vec.size();i++){ if(vec[i] <= vec[i-1]) return false; } return true; } };
第二种:定义全局变量,记录遍历过的最大值。相当于边遍历边比较。
/** * 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 { public: long long max_value = LONG_MIN;//长整型的最小值 bool isValidBST(TreeNode* root) { //终止条件,中序遍历 if(!root) return true; //左子树 bool left = isValidBST(root->left); if(!left) return false;//如果左子树已经不是二叉搜索树,可以直接返回,没有也可以。 //中 if(max_value >= root->val) return false; max_value = root->val; //右 bool right = isValidBST(root->right); return left && right; } };
第三种:题目如果节点数值包含长整型的最小值怎么办?没有比这个更小的,那么在if(max_value >= root->val)会出错。所以,最好不用全局变量,进一步优化,使用双指针,用一个指针记录前一个节点,比较逻辑在中间节点处完成。
/** * 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 { public: TreeNode* pre = nullptr; bool isValidBST(TreeNode* root) { //终止条件 if(!root) return true; //不为空,中序遍历 bool left = isValidBST(root->left);//左 if(!left) return false; //中 if(pre!=nullptr && pre->val >= root->val){ return false; } pre = root;//更新 //右 bool right = isValidBST(root->right); return left && right; } };
迭代法:已经获取思路,进行中序遍历。那么中序遍历的迭代实现:记录 三十六【二叉树迭代遍历】 有两种方式,一个区别于前后序迭代,一个是统一迭代模版(空指针标记法)。
根据思路和统一迭代模版,代码实现:
/** * 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 { public: bool isValidBST(TreeNode* root) { stack<TreeNode*> st; if(!root) return true; st.push(root); TreeNode* pre = nullptr; while(!st.empty()){ TreeNode* cur = st.top();st.pop(); if(cur != nullptr){ if(cur->right) st.push(cur->right);//右 st.push(cur);//中 st.push(nullptr);//标记 if(cur->left) st.push(cur->left); }else{ TreeNode* node = st.top();st.pop(); if(pre != nullptr && pre->val >= node->val){ return false; } pre = node; } } return true; } };
对比参考给出的迭代法:
class Solution { public: bool isValidBST(TreeNode* root) { stack<TreeNode*> 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; } };
【98.验证二叉搜索树】:
(欢迎指正,转载标明出处)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。