Skip to main content

98. Validate Binary Search Tree

分析

BST 中序遍历为升序

注意下 这个解法是错误的

function isValidBST(root: TreeNode | null): boolean {
if (!root) {
return true
}
console.log(root.val, root.left?.val, root.right?.val)
if (root.left && root.left.val >= root.val) {
return false
}
if (root.right && root.right.val <= root.val) {
return false
}

return isValidBST(root.left) && isValidBST(root.right)
};

无法应对下面的结构 Pasted image 20220430211451.png

题解

function isValidBST(root: TreeNode | null): boolean {
let prev = -Infinity

const dfs = (node: TreeNode | null) => {
if(!node) {
return true
}
if (!dfs(node.left)) {
return false
}
if (prev >= node.val) {
return false
}
prev = node.val
if (!dfs(node.right)) {
return false
}

return true
}

return dfs(root)
};