LeetCode.530.Minimum Absolute Difference in BST 非负BST的最小绝对差

题目描述

530 Minimum Absolute Difference in BST https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

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.

解题过程

求 非负二叉搜索树BST 的最小绝对差。

和 LeetCode.783.Minimum Distance Between BST Nodes BST的最小差值 几乎相同，一个是最小绝对差，一个是最小差值。

二叉搜索树的中序遍历序列是一个升序序列，这是二叉搜索树的一个重要性质，巧妙利用这一性质可以解决一系列二叉搜索树问题。所以可以把BST看成和有序数组是等价的，一看到BST马上就要想到是有序数组。

做过几道 BST 题后，已经可以熟练想到BST的上述性质，所以也马上就知道了非负升序数组中的最小绝对差肯定是在两两相邻的元素之间。 所以中序遍历，遍历过程中记住上一个遍历的结点，并不断计算相邻结点之差更新全局变量 min 即可。 时间复杂度 O(n)，空间复杂度 O(n) 也可以递归写，更简单，而且我看耗时最少的反而是递归的。

private static class SolutionV2020 {
    private Integer minDif;
    public int getMinimumDifference(TreeNode root) {
        minDif = null;
        InOrderTraverse(root);
        return minDif;
    }

    private void InOrderTraverse(TreeNode root) {
        if (null == root) {
            return;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root; // 当前节点
        TreeNode pre = null; // 前一个遍历的结点
        while (!stack.isEmpty() || null != cur) {
            while (null != cur) {
                stack.push(cur);
                cur = cur.left;
            }
            if (!stack.isEmpty()) {
                cur = stack.pop();
                if (null != pre) {
                    minDif = null != minDif ? Math.min(minDif, cur.val - pre.val) : cur.val - pre.val;
                }
                pre = cur;
                cur = cur.right;
            }
        }
    }
}

GitHub代码

algorithms/leetcode/leetcode/_530_MinimumAbsoluteDifferenceInBST.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_530_MinimumAbsoluteDifferenceInBST.java