day57（1.8）——leetcode面试经典150

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

530. 二叉搜索树的最小绝对值

题目：

题解：

一开始用的笨办法：

/** * 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 int getMinimumDifference(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); List<Integer> list = new ArrayList<>(); while(queue.size()>0) { int size = queue.size(); for(int i=0;i<size;i++) { TreeNode node = queue.poll(); list.add(node.val); if(node.left != null) { queue.offer(node.left); } if(node.right != null) { queue.offer(node.right); } } } list.sort(null); int minn = Integer.MAX_VALUE; for(int i=1;i<list.size();i++) { minn = Math.min(minn, list.get(i)-list.get(i-1)); } return minn; } }

妙哉，用中序遍历

/** * 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 int minn = Integer.MAX_VALUE; public int pre = Integer.MIN_VALUE/2; public int getMinimumDifference(TreeNode root) { dfs(root); return minn; } public void dfs(TreeNode root) { if(root == null) { return ; } dfs(root.left); minn = Math.min(minn, root.val-pre); pre = root.val; dfs(root.right); } }