98. 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例1:
输入:
2
/ \
1 3
输出: true
示例2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
-
1. 递归法
思路：
- 递归终止条件为当前节点为空
- 判断当前节点是否满足二叉树性质（左子树都小于根节点 & 右子树都大于根节点）
- 递归判断左右子树是否满足条件
- 注意：要判断右子树中所有节点都要大于根节点才可以
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValidBST(TreeNode root, long minVal, long maxVal) {
if (root == null) return true;
if (root.val >= maxVal || root.val <= minVal) return false;
return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
}
复杂度分析：
时间复杂度：O(n), 需要遍历所有节点进行判断
空间复杂度：O(n), 递归深度可能达到n层
-
2. 迭代法
需要使用（中序遍历）LeetCode 94. 二叉树的中序遍历 - 简书
思路： 二叉搜索树中序遍历后的结果一定是从小到达排列的
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
long res = Long.MIN_VALUE;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (cur.val < res) return false;
else res = cur.val;
cur = cur.right;
}
return true;
}
复杂度分析：
时间复杂度：O(n), 最坏情况下我们需要遍历每个元素添加到stack中
空间复杂度：O(n), 栈中需要存储 n 个元素
-
3. 中序遍历
思路：
- 创建 list，递归进行中序遍历，将每个节点的值添加到 list中
- 遍历 list， 判断是否是从小到大进行排序的，如果是则一定是二叉搜索树，否则一定不是
public boolean isValidBST(TreeNode root) {
List<Long> list = new ArrayList<>();
helper(root, list);
for (int i = 1; i < list.size(); i++) {
if (list.get(i) - list.get(i - 1) <= 0) return false;
}
return true;
}
private void helper(TreeNode root, List<Long> list) {
if (root == null) return;
helper(root.left, list);
list.add((long) root.val);
helper(root.right, list);
}
复杂度分析：
- 时间复杂度：O(n + n), 需要遍历每个节点进行递归比较，最后还需要遍历 list 查看顺序
- 空间复杂度：O(n + n), 中序遍历过程中使用了递归，并且还需要创建大小为 n 的 list
-
源码
-
我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正
- Github
