345 lines
8.6 KiB
Markdown
345 lines
8.6 KiB
Markdown
## 题目地址
|
||
https://leetcode.com/problems/validate-binary-search-tree/description/
|
||
|
||
## 题目描述
|
||
```
|
||
Given a binary tree, determine if it is a valid binary search tree (BST).
|
||
|
||
Assume a BST is defined as follows:
|
||
|
||
The left subtree of a node contains only nodes with keys less than the node's key.
|
||
The right subtree of a node contains only nodes with keys greater than the node's key.
|
||
Both the left and right subtrees must also be binary search trees.
|
||
|
||
|
||
Example 1:
|
||
|
||
2
|
||
/ \
|
||
1 3
|
||
|
||
Input: [2,1,3]
|
||
Output: true
|
||
Example 2:
|
||
|
||
5
|
||
/ \
|
||
1 4
|
||
/ \
|
||
3 6
|
||
|
||
Input: [5,1,4,null,null,3,6]
|
||
Output: false
|
||
Explanation: The root node's value is 5 but its right child's value is 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：
|
||
|
||
```c++
|
||
// 递归
|
||
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:
|
||
|
||
```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<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：
|
||
|
||
```C++
|
||
/**
|
||
* 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:
|
||
|
||
```Python
|
||
# 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)
|
||
}
|
||
```
|
||
|
||
## 相关题目
|
||
|
||
[230.kth-smallest-element-in-a-bst](./230.kth-smallest-element-in-a-bst.md)
|