关于leetcode:leetcode-530-Minimum-Absolute-Difference-in-BST二叉搜索树的最小绝对差-简单

3次阅读

共计 856 个字符，预计需要花费 3 分钟才能阅读完成。

给你一个二叉搜寻树的根节点 root，返回树中任意两不同节点值之间的最小差值。

差值是一个负数，其数值等于两值之差的绝对值。

示例 1：

输出：root = [4,2,6,1,3]

输入：1

示例 2：

输出：root = [1,0,48,null,null,12,49]

输入：1

提醒：

树中节点的数目范畴是 [2, 104]
0 <= Node.val <= 105

起源：力扣（LeetCode）
链接：https://leetcode.cn/problems/…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

这道题给咱们一棵二叉搜寻树，让咱们求任意个节点值之间的最小相对差。因为 BST 的左 < 根 < 右的性质可知，如果依照中序遍历会失去一个有序数组，那么最小相对差必定在置信的两个节点值之之间产生。所以咱们的做法就是对 BST 进行中序遍历，而后以后节点值和之前节点值求相对差并更新后果 res。须要留神的是在解决第一个节点值时，没有前节点所以不能求相对差。咱们用变量 pre 来示意前节点，将其初始化为 -1（节点值不为正数），咱们就晓得 pre 是否存在。

public class Solution {public int getMinimumDifference(TreeNode root) {int[] res = {Integer.MAX_VALUE};
        int[] pre = {-1};
        inorder(root, pre, res);
        return res[0];
    }

    void inorder(TreeNode root, int[] pre, int[] res) {if (root == null) {return;}
        inorder(root.left, pre, res);
        if (pre[0] != -1) {res[0] = Math.min(res[0], root.val - pre[0]);
        }
        pre[0] = root.val;
        inorder(root.right, pre, res);
    }
}