
问题
给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。
输入:
1
\
3
/
2输出:
1
解释:
最小绝对差为1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。
注意: 树中至少有2个节点。
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
Input:
1
\
3
/
2Output:
1
Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
Note: There are at least two nodes in this BST.
示例
public class Program { public static void Main(string[] args) { var root = new TreeNode(4) { left = new TreeNode(8), right = new TreeNode(1) }; var res = GetMinimumDifference(root); Console.WriteLine(res); Console.ReadKey(); } public static int GetMinimumDifference(TreeNode root) { var list = new List<int>(); PreOrder(root, ref list); var res = int.MaxValue; list.Sort(); for(var i = 0; i < list.Count - 1; i++) { res = Math.Min(res, list[i + 1] - list[i]); } return res; } public static void PreOrder(TreeNode root, ref List<int> list) { if(root == null) return; list.Add(root.val); PreOrder(root?.left, ref list); PreOrder(root?.right, ref list); } public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } } }
以上给出1种算法实现,以下是这个案例的输出结果:
3
分析:
对于该题来说,虽然使用了运行库 list.Sort() 排序,但 GetMinimumDifference 方法中最耗时且最重要的步骤是 res = Math.Min(res, list[i + 1] – list[i]) 这一句代码,所以我认为以上算法的时间复杂度应当为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4123。