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种算法实现，以下是这个案例的输出结果：

分析：

对于该题来说，虽然使用了运行库 list.Sort() 排序，但 GetMinimumDifference 方法中最耗时且最重要的步骤是 res = Math.Min(res, list[i + 1] - list[i]) 这一句代码，所以我认为以上算法的时间复杂度应当为： $O(n)$ 。

巴特西

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

最新文章

热门文章