JAVA练习311- 验证二叉搜索树

题目概览给你一个二叉树的根节点root判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下节点的左子树只包含严格小于当前节点的数。节点的右子树只包含严格大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1输入root [2,1,3]输出true示例 2输入root [5,1,4,null,null,3,6]输出false解释根节点的值是 5 但是右子节点的值是 4 。提示树中节点数目范围在[1, 104]内-2^31 Node.val 2^31 - 1来源98. 验证二叉搜索树 - 力扣LeetCode解题分析方法一递归令当前节点为 cur左右节点为 left 和 right那么一定满足left 的值小于 cur 的值right 的值大于 cur 的值如果 cur 的上面节点有右节点left 的值要大于最大的右节点如果 cur 的上面节点有左节点right 的值要小于最小的左节点令最大右节点值和最小左节点值为 max 和 min可得max left curcur right min因此我们可以用递归实现将 min 和 max 作为参数往下传即可。时间复杂度O(n)空间复杂度O(n)/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public boolean isValidBST(TreeNode root) { return isValidBST(root, Long.MAX_VALUE, Long.MIN_VALUE); } public boolean isValidBST(TreeNode root, long max, long min) { if (root null) { return true; } if (root.val max || root.val min) { return false; } return isValidBST(root.left, root.val, min) isValidBST(root.right, max, root.val); } }方法二中序遍历因为中序遍历时 左-根-右 的顺序遍历出来的数一定是递增的因此我们只需要前后的数是否递增即可。中序遍历可以用栈来实现这里不细讲。时间复杂度O(n)空间复杂度O(n)/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public boolean isValidBST(TreeNode root) { DequeTreeNode dq new LinkedList(); long pre Long.MIN_VALUE; while(root ! null || !dq.isEmpty()) { while(root ! null) { dq.push(root); root root.left; } TreeNode node dq.pop(); if (node.val pre) { return false; } pre node.val; root node.right; } return true; } }