给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左只包含严格小于 当前节点的数。
- 节点的右子树只包含 严格大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
- 树中节点数目范围在
[1, 104]内 -231 <= Node.val <= 231 - 1
1. 算法核心思想：降维打击
这道题如果直接用递归在树上比对大小，其实非常容易踩坑（比如只判断了当前节点和左右孩子的大小，却忽略了右子树里有个极小的值比总根节点还要小）。
采用了“降维打击”的思想，巧妙绕开了复杂的树结构比对：
- 根据 BST 的定义：左子树 < 根节点 < 右子树。
- 而二叉树的中序遍历顺序恰好是：左子树 -> 根节点 -> 右子树。
- 这意味着：如果我们对一棵合法的 BST 进行中序遍历，得到的数字序列必须是“从小到大严格递增”的！
因此，算法分为两步走：
- 拍扁它：用中序遍历（
func）把这棵二维的树“拍扁”成一个一维的数组。 - 检查它：遍历这个数组，看看它是不是严格从小到大排列的。如果发现有后面的数字小于或等于前面的数字（
v[i] <= v[i - 1]），直接判为不合格。
class Solution {
public:
bool isValidBST(TreeNode* root) {
// 1. 空树也是合法的二叉搜索树
if (root == NULL) {
return true;
}
// 2. 用一个数组来接收中序遍历的结果
vector<int> v;
func(v, root);
// 3. 遍历验证数组是否严格单调递增
for (int i = 1; i < v.size(); i++) {
// 注意：题目要求“严格”大于/小于，所以如果有相等的值（<=），也算无效 BST
if (v[i] <= v[i - 1]) {
return false;
}
}
// 全部通过考验，是合法的 BST
return true;
}
// 辅助函数：标准的二叉树中序遍历（左 -> 根 -> 右）
void func(vector<int>& v, TreeNode* node) {
if (node == NULL) {
return;
}
func(v, node->left); // 先去左边收集更小的值
v.push_back(node->val); // 把当前节点的值存入数组
func(v, node->right); // 再去右边收集更大的值
}
};
2. 复杂度分析
- 时间复杂度：O(N)。其中 N 为二叉树的节点个数。我们需要遍历整棵树将所有节点存入数组（耗时 O(N)），然后再遍历一次长度为 N 的数组（耗时 O(N)）。整体时间复杂度为线性的 O(N)。
- 空间复杂度：O(N)。我们开辟了一个额外的数组
v来保存 N 个节点的值，加上递归调用产生的系统栈空间（最坏情况下为 O(N)），总空间开销为 O(N)。