Day111 | 灵神 | 二叉树 | 验证二叉搜索树
98.验证二叉搜索树
98. 验证二叉搜索树 - 力扣（LeetCode）
方法一：前序遍历
递归函数传入合法的左右边界，只有当前结点是合法的边界，才是二叉搜索树，否则就返回false
对于左子树就传入当前结点的左边界，和当前结点的值作为右边界，从而验证左子树是一颗二叉搜索树
对于右子树就传入当前结点的右边界，和当前结点的值作为左边界，从而验证右子树是一颗二叉搜索树
只有当前结点符合条件并且左右子树也都是二叉搜索树才会返回true
灵神前序遍历代码：
class Solution {
public:bool isValidBST(TreeNode* root, long long left = LLONG_MIN, long long right = LLONG_MAX) {if (root == nullptr) {return true;}long long x = root->val;return left < x && x < right &&isValidBST(root->left, left, x) &&isValidBST(root->right, x, right);}
};
复杂度分析
- 时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。
- 空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。
方法二：中序遍历
二叉树搜索树的中序遍历是一个有序序列，记录前一个值，如果当前结点的值比前一个值小就是false
class Solution {
public:TreeNode *pre=nullptr;bool tra(TreeNode *t){if(t==nullptr)return true;bool l=tra(t->left);if(pre!=nullptr)if(t->val<=pre->val)return false;pre=t;bool r=tra(t->right);return l&&r;}bool isValidBST(TreeNode* root) {return tra(root);}
};
灵神中序遍历代码：
class Solution {long long pre = LLONG_MIN;
public:bool isValidBST(TreeNode* root) {if (root == nullptr) {return true;}if (!isValidBST(root->left) || root->val <= pre) {return false;}pre = root->val;return isValidBST(root->right);}
};
复杂度分析
- 时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。
- 空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。
方法三：后序遍历
灵神后序遍历代码：
class Solution {pair<long long, long long> dfs(TreeNode* node) {if (node == nullptr) {return {LLONG_MAX, LLONG_MIN};}auto[l_min, l_max] = dfs(node->left);auto[r_min, r_max] = dfs(node->right);long long x = node->val;// 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了if (x <= l_max || x >= r_min) {return {LLONG_MIN, LLONG_MAX};}return {min(l_min, x), max(r_max, x)};}public:bool isValidBST(TreeNode* root) {return dfs(root).second != LLONG_MAX;}
};
复杂度分析
- 时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。
- 空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。
灵神点评
- 前序遍历在某些数据下不需要递归到叶子节点就能返回（比如根节点左儿子的值大于根节点的值，左儿子就不会继续往下递归了），而中序遍历和后序遍历至少要递归到一个叶子节点。从这个角度上来说，前序遍历是最快的。
- 中序遍历很好地利用了二叉搜索树的性质，使用到的变量最少。
- 后序遍历的思想是最通用的，即自底向上计算子问题的过程。想要学好动态规划的话，请务必掌握自底向上的思想。
