题目描述给你一个二叉树的根节点root判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下节点的左子树只包含严格小于当前节点的数。节点的右子树只包含严格大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1输入root [2,1,3]输出true示例 2输入root [5,1,4,null,null,3,6]输出false解释根节点的值是 5 但是右子节点的值是 4 。解题思路方法一上下界递归推荐我的思路递归时携带一个开区间(low, high)表示当前节点允许的取值范围根节点初始区间为(-∞, ∞)进入左子树时上界收紧为当前节点值即(low, node-val)进入右子树时下界收紧为当前节点值即(node-val, high)每个节点检查是否落在区间内不满足直接返回false代码实现class Solution { public: bool isValidBST(TreeNode* root) { return check(root, nullptr, nullptr); } bool check(TreeNode* node, TreeNode* low, TreeNode* high) { if (node nullptr) return true; if (low ! nullptr node-val low-val) return false; if (high ! nullptr node-val high-val) return false; return check(node-left, low, node) check(node-right, node, high); } };复杂度分析时间O(n)每个节点访问一次空间O(h)递归栈深度h为树高。最坏链状O(n)平衡树O(log n)优缺点优点时间最优且发现非法节点时可提前剪枝返回逻辑清晰直接对应 BST 定义缺点递归写法链状树时栈深O(n)方法二中序遍历递归思路BST 的中序遍历结果严格递增。用一个prev指针记录上一个访问的节点遍历时若prev-val node-val则非法。代码实现class Solution { public: bool isValidBST(TreeNode* root) { TreeNode* prev nullptr; return inorder(root, prev); } bool inorder(TreeNode* node, TreeNode* prev) { if (node nullptr) return true; if (!inorder(node-left, prev)) return false; if (prev ! nullptr prev-val node-val) return false; prev node; return inorder(node-right, prev); } };复杂度分析时间O(n)空间O(h)递归栈优缺点优点思路直观就是检查是否严格递增一旦发现逆序立即返回可剪枝代码简洁缺点需要维护prev状态得用引用传递TreeNode*否则回溯后prev丢失同样有递归栈开销方法三中序遍历迭代 / Morris思路用显式栈模拟中序遍历或使用Morris 遍历利用叶子节点的空右指针做线索把空间降到O(1)。代码实现显式栈版class Solution { public: bool isValidBST(TreeNode* root) { stackTreeNode* st; TreeNode* prev nullptr; TreeNode* cur root; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); if (prev ! nullptr prev-val cur-val) return false; prev cur; cur cur-right; } return true; } };代码实现Morris 版空间 O(1)class Solution { public: bool isValidBST(TreeNode* root) { TreeNode* prev nullptr; TreeNode* cur root; while (cur ! nullptr) { if (cur-left nullptr) { if (prev ! nullptr prev-val cur-val) return false; prev cur; cur cur-right; } else { // 找左子树最右节点前驱 TreeNode* pred cur-left; while (pred-right ! nullptr pred-right ! cur) { pred pred-right; } if (pred-right nullptr) { pred-right cur; // 建线索 cur cur-left; } else { pred-right nullptr; // 拆线索 if (prev ! nullptr prev-val cur-val) return false; prev cur; cur cur-right; } } } return true; } };复杂度分析版本时间空间显式栈O(n)O(h)MorrisO(n)O(1)优缺点优点迭代版避免递归栈溢出适合超深树Morris 版空间O(1)面试加分项缺点Morris 代码复杂容易写错建线索 / 拆线索Morris 会临时修改树结构虽会还原但多线程场景不安全方法四暴力递归每个节点独立验证子树思路对每个节点检查其左子树最大值 节点值 右子树最小值。可写辅助函数求子树最值。代码实现class Solution { public: bool isValidBST(TreeNode* root) { if (root nullptr) return true; if (maxVal(root-left) root-val) return false; if (minVal(root-right) root-val) return false; return isValidBST(root-left) isValidBST(root-right); } long long maxVal(TreeNode* node) { if (node nullptr) return LLONG_MIN; return max({(long long)node-val, maxVal(node-left), maxVal(node-right)}); } long long minVal(TreeNode* node) { if (node nullptr) return LLONG_MAX; return min({(long long)node-val, minVal(node-left), minVal(node-right)}); } };复杂度分析时间O(n²)每个节点都要遍历一次其子树求最值空间O(h)递归栈不含重复子问题优缺点优点思路最直观直接照搬 BST 定义容易想到适合先写出朴素解再优化缺点时间O(n²)链状树时性能差大量重复计算方法对比总结方法时间空间是否剪枝推荐度上下界递归O(n)O(h)✅⭐⭐⭐⭐⭐中序递归O(n)O(h)✅⭐⭐⭐⭐⭐中序迭代O(n)O(h)✅⭐⭐⭐⭐MorrisO(n)O(1)✅⭐⭐⭐⭐暴力递归O(n²)O(h)❌⭐⭐
