Open
Description
中序遍历
二叉搜索树需要满足以下三个条件：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
- 二叉搜索树在中序遍历时得到的序列一定是升序的
- 进行中序遍历，判断当前节点是否大于前一个节点
- 如果比前一个大，说明满足，则继续遍历，否则直接返回 false
递归
const isValidBST = function(root) {
let prev = -Infinity
let result = true
function inorder(root) {
if (root === null) return
inorder(root.left)
if (root.val <= prev) {
result = false
return
}
prev = root.val
inorder(root.right)
}
inorder(root)
return result
}- 时间复杂度: O(n)
- 空间复杂度: O(n)
迭代
递归隐式地维护了一个栈，在迭代的时候我们需要显式地将这个栈模拟出来。
const isValidBST = function (root) {
const stack = []
let prev = -Infinity
while (root || stack.length) {
while (root) {
stack.push(root)
root = root.left
}
root = stack.pop()
if (root.val <= prev) {
return false
}
prev = root.val
root = root.right
}
return true
}- 时间复杂度: O(n)
- 空间复杂度: O(n)