这是悦乐书的第 253 次更新, 第 266 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 120 题(顺位题号是 530). 给定具有非负值的二叉搜索树, 找到任意两个节点的值之间的最小绝对差. 例:
输入:
- 1
- \
- 3
- /
- 2
输出: 1
说明: 最小绝对差值为 1, 即 2 和 1 之间 (或 2 和 3 之间) 的差值.
注意: 此 BST 中至少有两个节点.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
题目的要求是任意两个节点值之间的绝对值最小, 所以间接变成了求一组数据的最小绝对值. 使用栈 (或者队列) 遍历所有节点, 将所有节点值存入 list 中, 然后将 list 转为 Integer 类型的数组, 再将数组排序, 然后计算相邻两元素的绝对值, 找出其中的最小值.
- public int getMinimumDifference(TreeNode root) {
- List<Integer> list = new ArrayList<Integer>();
- Stack<TreeNode> stack = new Stack<TreeNode>();
- stack.push(root);
- while (!stack.isEmpty()) {
- TreeNode node = stack.pop();
- if (node.left != null) {
- stack.push(node.left);
- }
- list.add(node.val);
- if (node.right != null) {
- stack.push(node.right);
- }
- }
- Integer[] nums = (Integer[])list.toArray(new Integer[list.size()]) ;
- Arrays.sort(nums);
- int min = Math.abs(nums[0]-nums[1]);
- for (int i=0; i<nums.length-1; i++) {
- min = Math.min(Math.abs(nums[i]-nums[i+1]), min);
- }
- return min;
- }
03 第二种解法
我们可以利用 BST 的中序遍历特性, BST 中序遍历的节点是左根右排列, 是有序的, 递增的一列数据. 因此, 我们可以利用递归方法, 中序遍历其节点, 计算其相邻两个节点值的绝对值. 因此我们需要保留其前一个节点的节点值, 使用一个全局变量来记录. 如果 prev 为 null, 表示当前遍历到的为第一个节点, 不为 null 的时候, 就可以直接计算最小绝对值了.
- Integer prev = null;
- int min = 0;
- public int getMinimumDifference2(TreeNode root) {
- traverse(root);
- return min;
- }
- private void traverse(TreeNode root) {
- if (root == null) {
- return;
- }
- traverse(root.left);
- if (prev != null) {
- if (min == 0) {
- min = Math.abs(root.val - prev);
- } else {
- min = Math.min(Math.abs(root.val - prev), min);
- }
- }
- prev = root.val;
- traverse(root.right);
- }
04 第三种解法
第二种解法还可以再优化下, 将递归方法内置, 同时 min 初始值为 int 类型的最大值, 而不是第二种解法的 0, 可以省去一步判断.
- Integer prev2 = null;
- int min2 = Integer.MAX_VALUE;
- public int getMinimumDifference3(TreeNode root) {
- if (root == null) {
- return min2;
- }
- getMinimumDifference3(root.left);
- if (prev2 != null) {
- min2 = Math.min(Math.abs(root.val - prev2), min2);
- }
- prev2 = root.val;
- getMinimumDifference3(root.right);
- return min2;
- }
05 小结
算法专题目前已日更超过三个月, 算法题文章 120 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/b919704582f8