★【二叉搜索树（中序遍历特性）】【 ★递归+双指针】Leetcode 98. 验证二叉搜索树

---------------🎈🎈题目链接🎈🎈-------------------

二叉搜索树

---

98. 验证二叉搜索树

---

解法1 笨 中序递归遍历为一个数组 然后判断数组是不是升序排列就可以

二叉搜索树的特性：中序遍历是单调递增的

时间复杂度：
中序遍历二叉搜索树的时间复杂度为 O(n)，其中 n 是二叉树中节点的数量。
检查列表是否按升序排列的时间复杂度为 O(n)。
因此，总的时间复杂度为 O(n)。

空间复杂度：
存储节点值的列表的空间复杂度为 O(n)，因为需要存储整个树的节点值。
递归调用时的栈空间复杂度取决于树的高度，最坏情况下为 O(n)，平均情况下为 O(log 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) {// 中序递归遍历为一个数组 然后判断数组是不是升序排列就可以List<Integer> mylist = new ArrayList<>();helper(root,mylist);for(int i = 0; i < mylist.size(); i++){if(i>0 && (long)mylist.get(i)-(long)mylist.get(i-1) <= 0){return false;}}return true;}public void helper(TreeNode root,List<Integer> mylist){if(root == null) return ;helper(root.left,mylist);mylist.add(root.val);helper(root.right,mylist);}
}

★解法2 不使用数组 递归法

另一个题也是这样 530. 二叉搜索树的最小绝对差

class Solution {TreeNode pre = null;  public boolean isValidBST(TreeNode root) {// 不用数组直接用二叉树结构进行判断if(root == null) return true;  // 终止条件// 中序遍历顺序 当前的和前一个进行比较boolean left = isValidBST(root.left); // 左if(pre!= null && root.val <= pre.val){ // 中return false;}pre = root;boolean right = isValidBST(root.right); //右if(left && right) return true;else return false;}
}