[M二叉树] lc98. 验证二叉搜索树(dfs+多方法+前中后序+算法思维)

1. 题目来源

链接：98. 验证二叉搜索树

题单：

• 【题单】链表、二叉树与一般树（前后指针/快慢指针/DFS/BFS/直径/LCA）
  • 二、二叉树
    • §2.9 二叉搜索树

2. 题目解析

很经典的题目哈，之前只知道是一个有序序列判断就行了，也没有怎么去深究。灵神讲了三种方法，结合 前中后 序来进行题目处理，也是蛮不错的想法哈。

思路：

递归的思路：

• 前序思路：
  • 对于当前节点来讲，值为 x，那么左子树的取值范围就应该是 $(left,x)$ 开区间，右子树的取值范围就应该是 $(x,right)$ 开区间。
  • 即采用前序遍历的方式，维护当前值是否处于 二叉搜索树 的取值范围即可判断它是否满足二叉搜索树即可。
  • 是否满足：当前值是否在开区间的取值范围内。
• 中序思路：
  • 对于当前节点来讲，只需要比上一个节点的值大，那么根据中序遍历的原理就能证明它是一颗二叉搜索树。
  • 判断过程在递归中进行完成。
  • 中序遍历过程中，需要记录一下上一个节点值是什么，并对上一个值进行判断。
    • 这里注意直接开全局变量进行维护哈，不然通过递归函数参数维护的是不会变的，意义有区别。
• 后序思路：
  • 因为先返回的左右子树信息，再到的根节点。对于根节点来讲，就需要判断左右子树的取值范围是否在根节点的要求范围之内。
    • 左子树取值范围不应该超过根节点。
    • 右子树取值范围不能小于根节点。
  • 基于此，代码需要处理一些细节情况、边界情况啥的。写起来麻烦，这里用处感觉比较小。不进行实现。
  • 重点体会一下这个：自底向上 进行信息传递、信息判断 的思路。

非递归思路：

• 中序遍历二叉树得到序列。
• 判断序列是否严格有序即可。

---

• 时间复杂度：$O(n)$
• 空间复杂度：$O(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:typedef long long LL;bool ok(TreeNode *root, LL left, LL right) {if (!root) return true;int x = root->val;return left < x && x < right && ok(root->left, left, x) && ok(root->right, x, right);}bool isValidBST(TreeNode* root) {return ok(root, -1e18, 1e18);}
};

---

中序遍历：

/*** 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:typedef long long LL;LL pre = -1e18;bool ok(TreeNode *root) {if (!root) return true;if (!ok(root->left)) return false;int x = root->val;if (x <= pre) return false;pre = x;return ok(root->right);}bool isValidBST(TreeNode* root) {return ok(root);}
};