合法二叉搜索树
难度:
标签:
题目描述
Implement a function to check if a binary tree is a binary search tree.
Example 1:
Input:
2
/ \
1 3
Output: true
Example 2:
Input:
5
/ \
1 4
/ \
3 6
Output: false
Explanation: Input: [5,1,4,null,null,3,6].
the value of root node is 5, but its right child has value 4.
代码结果
运行时间: 31 ms, 内存: 17.9 MB
/*
* 思路：
* 使用Java Stream来检查二叉搜索树的有效性并不常见，但我们可以将中序遍历的结果存储在列表中，然后检查列表是否严格升序。
*/
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public boolean isValidBST(TreeNode root) {
List<Integer> values = new ArrayList<>();
inorder(root, values);
return IntStream.range(0, values.size() - 1).allMatch(i -> values.get(i) < values.get(i + 1));
}
private void inorder(TreeNode node, List<Integer> values) {
if (node == null) {
return;
}
inorder(node.left, values);
values.add(node.val);
inorder(node.right, values);
}
}
解释
方法:
这个题解通过递归方式来判断二叉树是否为二叉搜索树（BST）。主要思路是使用辅助函数 isValid 来验证每个节点的值是否符合BST的定义。具体而言，每个节点的值必须大于其所有左子树节点的值并且小于其所有右子树节点的值。为了实现这一点，我们对每个节点设定一个值的范围，使用 min 和 max 两个参数记录当前节点值的有效范围。在递归过程中，对左子节点调用 isValid 时，更新最大值 max 为当前节点的值；对右子节点调用时，更新最小值 min 为当前节点的值。递归基是当遍历到空节点时，返回 true，因为空节点不违反BST的定义。如果节点的值不在当前的有效范围内，即大于等于 max 或小于等于 min，则返回 false。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在定义isValid函数时选择使用负无穷和正无穷作为初始的min和max值，这种方法在所有情况下都适用吗？
▷🦆
在递归函数中，如果节点的值恰好等于min或max，为什么这种情况返回false？是否与BST的定义有关？
▷🦆
递归检查左子树时，为什么可以确定新的max值为当前节点的值，而检查右子树时，新的min值为当前节点的值？这样的更新有可能遗漏某些情况吗？
▷