本文共 2002 字,大约阅读时间需要 6 分钟。
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
最容易想到的方法,由于是BST,直接中序遍历后即可得到排序后的list,再把排序后的list两两比较找出相差最小的值即可。
/*** Definition for a binary tree node.* public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }* }*/public class Solution { Listlist = new ArrayList (); public int getMinimumDifference(TreeNode root) { traverse(root); int min = Integer.MAX_VALUE; for(int i = 0; i < list.size() - 1; i++) { int absDiffer = Math.abs(list.get(i) - list.get(i+1)); min = absDiffer
由于BST本身子树间就是有序的,即可以通过递归等效实现中序遍历后两两比较的效果。代码如下:
/*** Definition for a binary tree node.* public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }* }*/public class Solution { private int min = Integer.MAX_VALUE; Integer prev = -1; public int getMinimumDifference(TreeNode root) { if(root == null) return min; getMinimumDifference(root.left); if(prev != -1) min = Math.min(min, Math.abs(prev - root.val)); prev = root.val; getMinimumDifference(root.right); return min; }}
而在discuss中有网友给出了如何实现非BST树时如何得出最小差值。思路就是将非BST树,利用API中的TreeSet将其转化为BST树再来进行两两比较,本质上和上面写法是一样的。
public class Solution { TreeSetset = new TreeSet<>(); int min = Integer.MAX_VALUE; public int getMinimumDifference(TreeNode root) { if (root == null) return min; if (!set.isEmpty()) { if (set.floor(root.val) != null) { min = Math.min(min, Math.abs(root.val - set.floor(root.val))); } if (set.ceiling(root.val) != null) { min = Math.min(min, Math.abs(root.val - set.ceiling(root.val))); } } set.add(root.val); getMinimumDifference(root.left); getMinimumDifference(root.right); return min; }}
转载地址:http://lijgj.baihongyu.com/