长春火车站什么时候解封,建立一个自己的网站,网站设计任务书范文,数字展厅企业展厅★【二叉搜索树#xff08;中序遍历特性#xff09;】【 ★递归双指针】Leetcode 98. 验证二叉搜索树 二叉搜索树 98. 验证二叉搜索树解法1 笨 中序递归遍历为一个数组 然后判断数组是不是升序排列就可以★解法2 不使用数组 递归法 ---------------#x1f388;#x1f38… ★【二叉搜索树中序遍历特性】【 ★递归双指针】Leetcode 98. 验证二叉搜索树 二叉搜索树 98. 验证二叉搜索树解法1 笨 中序递归遍历为一个数组 然后判断数组是不是升序排列就可以★解法2 不使用数组 递归法 ---------------题目链接-------------------
二叉搜索树 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) {// 中序递归遍历为一个数组 然后判断数组是不是升序排列就可以ListInteger mylist new ArrayList();helper(root,mylist);for(int i 0; i mylist.size(); i){if(i0 (long)mylist.get(i)-(long)mylist.get(i-1) 0){return false;}}return true;}public void helper(TreeNode root,ListInteger 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;}
}
