1. question: 验证二叉搜索树(中等)
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/validate-binary-search-tree
示例 1:
1 2
| 输入:root = [2,1,3] 输出:true
|
示例 2:
1 2 3
| 输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。
|
提示:
1 2
| 树中节点数目范围在[1, 104] 内 -231 <= Node.val <= 231 - 1
|
2. answers
这道题最开始想的是,按照题目中的标准来递归遍历二叉树。但是因为要保留子树的最大值和最小值,比较麻烦。后来限制条件太多,没做出来。后来想到的是中序遍历的顺序就是二叉搜索树的节点排序。
因此,只需要中序遍历,比如是否是递增即可。一种方法是遍历,然后保存遍历顺序,之后,再判断是否递增。代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| public class Solution_0068 {
public static void midOrder(TreeNode tn, List<Integer> result) {
if(tn == null) return;
midOrder(tn.left, result);
result.add(tn.val);
midOrder(tn.right, result); }
public static boolean isValidBST(TreeNode root) {
List<Integer> result = new ArrayList<>();
midOrder(root, result);
int temp = result.get(0); for (int i = 1; i < result.size(); i++) {
if(temp >= result.get(i)) return false;
temp = result.get(i); }
return true; }
public static void main(String[] args) { System.out.println();
TreeNode tn2 = new TreeNode(2); TreeNode tn1 = new TreeNode(1, tn2, tn2);
System.out.println(isValidBST(tn1)); } }
|
参考了题解,其实没必要保存序列,可以在遍历的时候,保存上一个节点的值,然后与当前节点比较即可。代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| public static long pre = Long.MIN_VALUE;
public static boolean isValidBST(TreeNode root) {
if(root == null) return true;
if(!isValidBST(root.left)) return false;
if(pre >= root.val) return false;
pre = root.val;
return isValidBST(root.right);
}
|
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。