98.validate-binary-search-tree.md

题目地址(98. 验证二叉搜索树)

https://leetcode-cn.com/problems/validate-binary-search-tree/

题目描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 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：

/* * @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} */varisValidBST=function(root){if(root===null)returntrue;if(root.left===null&&root.right===null)returntrue;conststack=[root];letcur=root;letpre=null;functioninsertAllLefts(cur){while(cur&&cur.left){constl=cur.left;stack.push(l);cur=l;}}insertAllLefts(cur);while((cur=stack.pop())){if(pre&&cur.val<=pre.val)returnfalse;constr=cur.right;if(r){stack.push(r);insertAllLefts(r);}pre=cur;}returntrue;};

C++ Code：

// 递归classSolution { public:boolisValidBST(TreeNode* root) { TreeNode* prev = nullptr; returnvalidateBstInorder(root, prev); } private:boolvalidateBstInorder(TreeNode* root, TreeNode*& prev) { if (root == nullptr) returntrue; if (!validateBstInorder(root->left, prev)) returnfalse; if (prev != nullptr && prev->val >= root->val) returnfalse; prev = root; returnvalidateBstInorder(root->right, prev); } }; // 迭代classSolution { public:boolisValidBST(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) returnfalse; prev = root; root = root->right; } returntrue; } };

Java Code:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */classSolution { publicbooleanisValidBST(TreeNoderoot) { Stack<Integer> stack = newStack<> (); TreeNodeprevious = 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 ) returnfalse; previous = root; root = root.right; } returntrue; } }

定义法

• 语言支持：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) {} * };*/// 递归classSolution { public:boolisValidBST(TreeNode* root) { returnhelper(root, LONG_MIN, LONG_MAX); } private:boolhelper(const TreeNode* root, long min, long max) { if (root == nullptr) returntrue; if (root->val >= max || root->val <= min) returnfalse; returnhelper(root->left, min, root->val) && helper(root->right, root->val, max); } }; // 循环classSolution { public:boolisValidBST(TreeNode* root) { if (root == nullptr) returntrue; 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) { returnfalse; } 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); } } } returntrue; } };

Python Code:

# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution: defisValidBST(self, root: TreeNode, area: tuple=(-float('inf'), float('inf'))) ->bool: """思路如上面的分析，用Python表达会非常直白 :param root TreeNode 节点 :param area tuple 取值区间 """ifrootisNone: returnTrueis_valid_left=root.leftisNoneor\ (root.left.val<root.valandarea[0] <root.left.val<area[1]) is_valid_right=root.rightisNoneor\ (root.right.val>root.valandarea[0] <root.right.val<area[1]) # 左右节点都符合，说明本节点符合要求is_valid=is_valid_leftandis_valid_right# 递归下去returnis_valid\ andself.isValidBST(root.left, (area[0], root.val))\ andself.isValidBST(root.right, (root.val, area[1]))

Java Code:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */classSolution { publicbooleanisValidBST(TreeNoderoot) { returnhelper(root, null, null); } privatebooleanhelper(TreeNoderoot, Integerlower, Integerhigher) { if (root == null) returntrue; if (lower != null && root.val <= lower) returnfalse; if (higher != null && root.val >= higher) returnfalse; if (!helper(root.left, lower, root.val)) returnfalse; if (!helper(root.right, root.val, higher)) returnfalse; returntrue; } }

JavaScript Code:

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } *//** * @param {TreeNode} root * @return {boolean} */varisValidBST=function(root){if(!root)returntrue;returnvalid(root);};functionvalid(root,min=-Infinity,max=Infinity){if(!root)returntrue;constval=root.val;if(val<=min)returnfalse;if(val>=max)returnfalse;returnvalid(root.left,min,val)&&valid(root.right,val,max);}

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

相关题目

230.kth-smallest-element-in-a-bst

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。