大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位金融行业的同学讲诉自己一位前同事被裁的经历，前同事是国内top2高校毕业的，依然无法摆脱被干掉的命运。自己虽然已经跳出这个行业但也只是苟着，感觉成长和赚大钱跟我们这代人中99%的人没关系了。
很多人都有类似的感觉。我们的职业成长仿佛已经脱离了个人努力的控制，长期的积累在面对裁员或新一轮的技术潮流面前，似乎变得不值一提。面对未来，厚积薄发的理论显得越来越空洞，变得不切实际。甚至对大多数人来说，不被裁员、保持稳定就已成为一种成功。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道高频面试题「验证二叉搜索树」。
题目描述
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。
举个例子：
输入：root = [2,1,3]
输出：true
思路解析
对二叉搜索树进行中序遍历，其节点值组成的序列是单调递增的。
比如对于下图的二叉搜索树进行中序遍历，得到一个单调递增的序列[1,2,3]。
验证一棵二叉树是否是二叉搜索树，我们可以直接对这棵树进行中序遍历，把遍历得到的节点值存到数组vals里，如果vals是单调递增的那么这棵树就是二叉搜索树。这里用到一个数组vals，我们在判断数组是否单调会用到两个索引，pre，cur = pre + 1，遍历整个数组如果vals[pre] < vals[cur]恒成立，说明数组是单调的。
我们可以对上面的流程进一步优化，不需要把节点的值存的数组里，定义一个全局变量pre_val存储中序遍历过程中上一个访问的值，可以一边遍历，一边比较当前访问的值和上一个访问的值pre_val的大小。只需要对二叉树的中序遍历稍加改造就可以实现。
下面我们给出c++和python的两种代码实现。
C++代码
/**
* 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) {
long long pre_val = LONG_MIN;
return isValidBST_help(root, pre_val);
}
bool isValidBST_help(TreeNode* root, long long& pre_val) {
if (!root) return true;
//左子树不满足二叉搜索树
if (!isValidBST_help(root->left, pre_val)) return false;
//根节点和上一个被访问的节点的值比较
if (root->val <= pre_val) return false;
//中序遍历更新pre_val
pre_val = root->val;
//右子树不满足二叉搜索树
if (!isValidBST_help(root->right, pre_val)) return false;
//整棵树满足二叉搜索树
return true;
}
};
python代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
self.preVal = float('-inf')
return self.isValidBSTHelper(root)
def isValidBSTHelper(self, root):
if not root:
return True
#左子树不满足二叉搜索树
if not self.isValidBSTHelper(root.left):
return False
#根节点和上一个被访问的节点的值比较
if root.val <= self.preVal:
return False
#中序遍历更新pre_val
self.preVal = root.val
#右子树是否满足二叉搜索树
return self.isValidBSTHelper(root.right)
复杂度分析
时间复杂度： 需要遍历整棵数，所以时间复杂度跟二叉树的总节点数相关。
空间复杂度： 验证的过程使用了递归，递归需要用到函数调用栈，函数栈的最大长度跟二叉树的高度相关。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
