1月19日代码随想录二叉搜索树的最小绝对差

530.二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点?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

思路?

中序遍历

二叉搜索树的中序遍历必定有序，所以我们只需要检查中序遍历每两个值之间的差即可，时间复杂度为O(n）

class Solution {
    public int getMinimumDifference(TreeNode root) {
        Deque<TreeNode> stack=new LinkedList<TreeNode>();
        int min=Integer.MAX_VALUE;
        int tmp=-1;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            if(root.val-tmp<min&&tmp!=-1){
                min=root.val-tmp;
            }
            tmp=root.val;
            root=root.right;
        }
        return min;
    }
}

中间这里存tmp的时候我本来给tmp设的初值为负最大值，但是这样在计算第一个min时会出错，所以我将它改为-1并在过程中加上判断是否为初值的过程。