一、题目粗心

给你一个二叉搜寻树的根节点 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是否存在。

三、解题办法

3.1 Java实现

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);    }}

四、总结小记

  • 2022/10/5 有时候生存不肯定比工作轻松