530. 二叉搜索树的最小绝对差(深搜)

前序遍历+排序. 时间复杂度: O(nlogn) 空间复杂度: O(n)

 1 class Solution {
 2     private int res=Integer.MAX_VALUE;
 3     private ArrayList<Integer> arry=new ArrayList<>();
 4     public int getMinimumDifference(TreeNode root){
 5         dfs(root); //前序遍历树的节点元素
 6         Collections.sort(arry); //排序
 7         for(int i=0;i<arry.size()-1;i++){ //最小绝对差肯定由大小相邻的两个元素产生
 8             int temp=Math.abs(arry.get(i+1)-arry.get(i));
 9             if(temp<res) res=temp;
10         }
11         return res;
12     }
13     void dfs(TreeNode root){
14         if(root==null) return;
15         arry.add(root.val);
16         dfs(root.left);
17         dfs(root.right);
18     }
19 }

没看到这是一棵二叉搜索树,中序遍历得到的就是从小到大排列的元素值,得出上一个元素和现有元素做差的绝对值,然后和上一个记录下的最小绝对差比较即可,时间复杂度: O(n),空间复杂度: O(1)

 1 class Solution {
 2     private int pre=Integer.MAX_VALUE; //设定初始值
 3     private int res=Integer.MAX_VALUE; //记录最小绝对差
 4     public int getMinimumDifference(TreeNode root){
 5         dfs(root);
 6         return res;
 7     }
 8     void dfs(TreeNode root){ //中序遍历
 9         if(root==null) return;
10         dfs(root.left);
11         res=Math.min(res,Math.abs(pre-root.val));
12         pre=root.val;
13         dfs(root.right);
14     }
15 }

530. 二叉搜索树的最小绝对差(深搜)

相关推荐