98. 验证二叉搜索树

输入：root = [2,1,3]
输出：true

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

二、方法一

递归利用二叉搜索树的性质进行判断

/*** 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.MIN_VALUE, Long.MAX_VALUE);}public boolean isValidBST(TreeNode root, long low, long uper) {if (root == null) {return true;}if (root.val <= low || root.val >= uper) {return false;}return isValidBST(root.left, low, root.val) && isValidBST(root.right, root.val,uper);}
}

复杂度分析

• 时间复杂度 : O(n)，其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)。

• 空间复杂度 : O(n)，其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 n ，递归最深达到 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) {if (root == null) {return true;}double temp = -Double.MAX_VALUE;Deque<TreeNode> stack = new ArrayDeque<>();while (!stack.isEmpty() || root != null) {while (root != null) {stack.push(root);root = root.left;}root = stack.poll();if (root.val <= temp) {return false;}temp = root.val;root = root.right;}return true;}
}

复杂度分析

• 时间复杂度 : O(n)，其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)。

• 空间复杂度 : O(n)，其中 nn 为二叉树的节点个数。栈最多存储 n 个节点，因此需要额外的 O(n)的空间。