中序遍历 + 迭代
解题思路
获取 BST 的中序遍历结果，BST 的中序遍历结果是一个升序列表；
判断中序遍历的结果是不是单调递增的；
复杂度
-
时间复杂度 :
O(n)，其中 n 为二叉树的节点个数，二叉树的每个节点最多被访问一次，因此时间复杂度为O(n)； -
空间复杂度 :
O(n)，其中 n 为二叉树的节点个数，栈最多存储 n 个节点，因此需要额外的O(n)的空间；
代码实现
var isValidBST = function (root) {
const inOrderDFS = (root) => {
if (root) {
inOrderDFS(root.left);
list.push(root.val);
inOrderDFS(root.right);
}
};
// 1. 获取 BST 的中序遍历结果
const list = [];
inOrderDFS(root);
// 2. 遍历 list 是否是升序序列
let prev = -Infinity;
for (let i = 0; i < list.length; i++) {
if (prev >= list[i]) return false;
prev = list[i];
}
return true;
};
中序遍历 + 递归
解题思路
递归判断是否是一个升序序列；
将上次访问的元素赋值给 prev 变量，每次把当前的节点 curr 与上次的 prev 比较，如果
prev.val >= root.val则说明不是 BST；
复杂度
-
时间复杂度 :
O(n)，其中 n 为二叉树的节点个数，二叉树的每个节点最多被访问一次，因此时间复杂度为O(n)； -
空间复杂度 :
O(n)，其中 n 为二叉树的节点个数，栈最多存储 n 个节点，因此需要额外的O(n)的空间；
代码实现
var isValidBST = function (root) {
const inOrderDFS = (root) => {
if (root) {
inOrderDFS(root.left);
if (prev && prev.val >= root.val) {
flag = false;
}
prev = root;
inOrderDFS(root.right);
}
}
let flag = true;
let prev = null;
inOrderDFS(root);
return flag;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 23. 合并 K 个升序链表
上一篇
评论
