# 0098. 验证二叉搜索树 ### 题目地址(98. 验证二叉搜索树) ### 题目描述 ``` 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1: 输入: 2 / \ 1 3 输出: true 示例 2: 输入: 5 / \ 1 4   / \   3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。   根节点的值为 5 ，但是其右子节点值为 4 。 ``` ### 前置知识 * 中序遍历 ### 公司 * 阿里 * 腾讯 * 百度 * 字节 ### 思路 #### 中序遍历 这道题是让你验证一棵树是否为二叉查找树（BST）。 由于中序遍历的性质`如果一个树遍历的结果是有序数组，那么他也是一个二叉查找树(BST)`, 我们只需要中序遍历，然后两两判断是否有逆序的元素对即可，如果有，则不是 BST，否则即为一个 BST。 #### 定义法 根据定义，一个结点若是在根的左子树上，那它应该小于根结点的值而大于左子树最小值；若是在根的右子树上，那它应该大于根结点的值而小于右子树最大值。也就是说，每一个结点必须落在某个取值范围： 1. 根结点的取值范围为（考虑某个结点为最大或最小整数的情况）：(long\_min, long\_max) 2. 左子树的取值范围为：(current\_min, root.value) 3. 右子树的取值范围为：(root.value, current\_max) ### 关键点解析 * 二叉树的基本操作（遍历） * 中序遍历一个二叉查找树（BST）的结果是一个有序数组 * 如果一个树遍历的结果是有序数组，那么他也是一个二叉查找树(BST) ### 代码 #### 中序遍历 * 语言支持：JS，C++, Java JavaScript Code： ```js /* * @lc app=leetcode id=98 lang=javascript * * [98] Validate Binary Search Tree */ /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {boolean} */ var isValidBST = function (root) { if (root === null) return true; if (root.left === null && root.right === null) return true; const stack = [root]; let cur = root; let pre = null; function insertAllLefts(cur) { while (cur && cur.left) { const l = cur.left; stack.push(l); cur = l; } } insertAllLefts(cur); while ((cur = stack.pop())) { if (pre && cur.val <= pre.val) return false; const r = cur.right; if (r) { stack.push(r); insertAllLefts(r); } pre = cur; } return true; }; ``` C++ Code： ``` // 递归 class Solution { public: bool isValidBST(TreeNode* root) { TreeNode* prev = nullptr; return validateBstInorder(root, prev); } private: bool validateBstInorder(TreeNode* root, TreeNode*& prev) { if (root == nullptr) return true; if (!validateBstInorder(root->left, prev)) return false; if (prev != nullptr && prev->val >= root->val) return false; prev = root; return validateBstInorder(root->right, prev); } }; // 迭代 class Solution { public: bool isValidBST(TreeNode* root) { auto s = vector(); TreeNode* prev = nullptr; while (root != nullptr || !s.empty()) { while (root != nullptr) { s.push_back(root); root = root->left; } root = s.back(); s.pop_back(); if (prev != nullptr && prev->val >= root->val) return false; prev = root; root = root->right; } return true; } }; ``` Java Code: ```java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isValidBST(TreeNode root) { Stack stack = new Stack<> (); TreeNode previous = null; while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); if (previous != null && root.val <= previous.val ) return false; previous = root; root = root.right; } return true; } } ``` #### 定义法 * 语言支持：C++，Python3, Java, JS C++ Code： ``` /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ // 递归 class Solution { public: bool isValidBST(TreeNode* root) { return helper(root, LONG_MIN, LONG_MAX); } private: bool helper(const TreeNode* root, long min, long max) { if (root == nullptr) return true; if (root->val >= max || root->val <= min) return false; return helper(root->left, min, root->val) && helper(root->right, root->val, max); } }; // 循环 class Solution { public: bool isValidBST(TreeNode* root) { if (root == nullptr) return true; auto ranges = queue>(); ranges.push(make_pair(LONG_MIN, LONG_MAX)); auto nodes = queue(); nodes.push(root); while (!nodes.empty()) { auto sz = nodes.size(); for (auto i = 0; i < sz; ++i) { auto range = ranges.front(); ranges.pop(); auto n = nodes.front(); nodes.pop(); if (n->val >= range.second || n->val <= range.first) { return false; } if (n->left != nullptr) { ranges.push(make_pair(range.first, n->val)); nodes.push(n->left); } if (n->right != nullptr) { ranges.push(make_pair(n->val, range.second)); nodes.push(n->right); } } } return true; } }; ``` Python Code: ``` # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isValidBST(self, root: TreeNode, area: tuple=(-float('inf'), float('inf'))) -> bool: """思路如上面的分析，用Python表达会非常直白 :param root TreeNode 节点 :param area tuple 取值区间 """ if root is None: return True is_valid_left = root.left is None or\ (root.left.val < root.val and area[0] < root.left.val < area[1]) is_valid_right = root.right is None or\ (root.right.val > root.val and area[0] < root.right.val < area[1]) # 左右节点都符合，说明本节点符合要求 is_valid = is_valid_left and is_valid_right # 递归下去 return is_valid\ and self.isValidBST(root.left, (area[0], root.val))\ and self.isValidBST(root.right, (root.val, area[1])) ``` Java Code: ```java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isValidBST(TreeNode root) { return helper(root, null, null); } private boolean helper(TreeNode root, Integer lower, Integer higher) { if (root == null) return true; if (lower != null && root.val <= lower) return false; if (higher != null && root.val >= higher) return false; if (!helper(root.left, lower, root.val)) return false; if (!helper(root.right, root.val, higher)) return false; return true; } } ``` JavaScript Code: ```javascript /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {boolean} */ var isValidBST = function (root) { if (!root) return true; return valid(root); }; function valid(root, min = -Infinity, max = Infinity) { if (!root) return true; const val = root.val; if (val <= min) return false; if (val >= max) return false; return valid(root.left, min, val) && valid(root.right, val, max); } ``` **复杂度分析** * 时间复杂度：$O(N)$ * 空间复杂度：$O(N)$ ### 相关题目 [230.kth-smallest-element-in-a-bst](/leetcode-solution/medium/230.kth-smallest-element-in-a-bst.md) 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/pkle97.jpg) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/98.validate-binary-search-tree.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.