.jpg)
627 字
3 分钟
验证二叉搜索树
题目描述
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 严格小于 当前节点的数。
- 节点的右子树只包含 严格大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
解题思路
- 递归边界检查：
- 传递当前节点允许的最小/最大值范围
- 左子树上限 = 当前节点值
- 右子树下限 = 当前节点值
- 中序遍历特性：
- BST中序遍历结果为严格递增序列
- 记录前驱节点值，确保当前节点 > 前驱
- 终止条件：
- 空节点视为有效BST
- 节点值超出范围立即返回false
关键洞察
- 范围传递机制：
- 根节点范围(-∞, +∞)
- 左子树范围(min, parent.val)
- 右子树范围(parent.val, max)
- 中序有序性：
- 无需存储完整遍历序列
- 动态比较前驱节点值即可
- 相等值处理：
- BST定义要求严格大于/小于
- 等值情况视为无效
- 子树独立性：
- 左/右子树需独立满足BST条件
- 递归天然支持子树验证
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 递归边界法 | O(n) | O(h) [树高, 最坏O(n)] |
| 中序迭代法 | O(n) | O(h) [栈空间] |
代码实现
递归法
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * 中序遍历优化版 * @link {https://leetcode.cn/problems/validate-binary-search-tree/} * @param {TreeNode} root * @return {boolean} */const isValidBST = (root) => { const stack = []; let prev = -Infinity; // 记录前驱节点值 let current = root;
while (current || stack.length) { // 深度优先访问左子树 while (current) { stack.push(current); current = current.left; }
current = stack.pop(); // 检查是否严格递增 if (current.val <= prev) return false; prev = current.val;
// 转向右子树 current = current.right; }
return true;};迭代法
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * 中序遍历优化版 * @link {https://leetcode.cn/problems/validate-binary-search-tree/} * @param {TreeNode} root * @return {boolean} */var isValidBST = function (root) { let prev = -Infinity
const inOrder = (node) => { if (!node) return true if (!inOrder(node.left)) return false if (node.val <= prev) return false prev = node.val return inOrder(node.right) }
return inOrder(root)};