C#LeetCode刷题之#530-二叉搜索树的最小绝对差(Minimum Absolute Difference in BST)

C#LeetCode刷题之#530-二叉搜索树的最小绝对差(Minimum Absolute Difference in BST)

问题

给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。

输入:

   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
    /
   2

Output:
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]) 这一句代码,所以我认为以上算法的时间复杂度应当为: O(n)​ 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4123

发表评论

登录后才能评论