二叉树:我是不是一棵二叉搜索树( 二 )


代码如下:
long long maxVal = LONG_MIN; // 因为后台测试数据中有int最小值bool isValidBST(TreeNode* root)

  • 确定终止条件
如果是空节点 是不是二叉搜索树呢?
是的 , 二叉搜索树也可以为空!
代码如下:
if (root == NULL) return true;
  • 确定单层递归的逻辑
中序遍历 , 一直更新maxVal , 一旦发现maxVal >= root->val , 就返回false , 注意元素相同时候也要返回false 。
代码如下:
bool left = isValidBST(root->left);// 左// 中序遍历 , 验证遍历的元素是不是从小到大if (maxVal < root->val) maxVal = root->val; // 中else return false;bool right = isValidBST(root->right);// 右return left 整体代码如下:
class Solution {public:long long maxVal = LONG_MIN; // 因为后台测试数据中有int最小值bool isValidBST(TreeNode* root) {if (root == NULL) return true;bool left = isValidBST(root->left);// 中序遍历 , 验证遍历的元素是不是从小到大if (maxVal < root->val) maxVal = root->val;else return false;bool right = isValidBST(root->right);return left}};以上代码是因为后台数据有int最小值测试用例 , 所以都把maxVal改成了longlong最小值 。
如果测试数据中有 longlong的最小值 , 怎么办?
不可能在初始化一个更小的值了吧 。 建议避免 初始化最小值 , 如下方法取到最左面节点的数值来比较 。
代码如下:
class Solution {public:TreeNode* pre = NULL; // 用来记录前一个节点bool isValidBST(TreeNode* root) {if (root == NULL) return true;bool left = isValidBST(root->left);if (pre != NULLpre = root; // 记录前一个节点bool right = isValidBST(root->right);return left}};最后这份代码看上去整洁一些 , 思路也清晰 。
迭代法可以用迭代法模拟二叉树中序遍历 , 对前中后序迭代法生疏的同学可以看这两篇二叉树:听说递归能做的 , 栈也能做! , 二叉树:前中后序迭代方式统一写法
迭代法中序遍历稍加改动就可以了 , 代码如下:
class Solution {public:bool isValidBST(TreeNode* root) {stack 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 != NULLpre = cur; //保存前一个访问的结点cur = cur->right;// 右}}return true;}};总结这道题目是一个简单题 , 但对于没接触过的同学还是有难度的 。
所以初学者刚开始学习算法的时候 , 看到简单题目没有思路很正常 , 千万别怀疑自己智商 , 学习过程都是这样的 , 大家智商都差不多 , 哈哈 。
只要把基本类型的题目都做过 , 总结过之后 , 思路自然就开阔了 。
「就酱 , 学到了的话 , 就转发给身边需要的同学吧!」
-------end-------
我将算法学习相关的资料已经整理到了
Github : , 里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图 , 可以fork到自己仓库有空看一看一定会有所收获 , 顺便给一个star支持一下吧!
我是程序员Carl , 哈工大师兄 , 先后在腾讯和百度打杂 , 这里每天8:35准时推送一道经典算法题目 , 我选择的每道题目都不是孤立的 , 而是由浅入深 , 环环相扣 , 帮你梳理算法知识脉络 , 轻松学算法!
【二叉树:我是不是一棵二叉搜索树】@代码随想录 期待你的关注