0098. 验证二叉搜索树 · ttttt

# 0098. 验证二叉搜索树 ## 题目地址(98. 验证二叉搜索树) <https://leetcode-cn.com/problems/validate-binary-search-tree/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 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： ``` <pre class="calibre18">``` /* * @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： ``` <pre class="calibre18">``` // 递归 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*>(); 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: ``` <pre class="calibre18">``` /** * 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<Integer> 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： ``` <pre class="calibre18">``` /** * 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<pair<long, long>>(); ranges.push(make_pair(LONG_MIN, LONG_MAX)); auto nodes = queue<const TreeNode*>(); 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: ``` <pre class="calibre18">``` # 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: ``` <pre class="calibre18">``` /** * 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: ``` <pre class="calibre18">``` /** * 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)O(N) - 空间复杂度：O(N)O(N)O(N) ## 相关题目 [230.kth-smallest-element-in-a-bst](230.kth-smallest-element-in-a-bst.html) 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。目前已经 37K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)