530. 二叉搜索树的最小绝对差(简单)

1，问题描述

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

**注意：**本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同

2，初步思考

​ 解法：搜索二叉树中序遍历时，数组是单调递增的，所以只用求俩俩差值最小就行

3，代码处理

import support.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class _530二叉搜索树的最小绝对差 {

    // 解法：中序遍历优化
    // 只用遍历一次即可
    public int getMinimumDifference_option(TreeNode root) {
        temp = null;
        min = Integer.MAX_VALUE;
        treeSlipMid_v2(root);
        return min;
    }

    Integer temp = null;

    private void treeSlipMid_v2(TreeNode root) {
        if (root == null) return;
        treeSlipMid_v2(root.left);
        if (temp != null) {
            min = Math.min(min, Math.abs(root.val - temp));
        }
        temp = root.val;
        treeSlipMid_v2(root.right);
    }

    // 中序遍历求解
    public int getMinimumDifference_mid(TreeNode root) {
        list = new ArrayList<>();
        treeSlipMid(root);
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < list.size(); i++) {
            min = Math.min(min, list.get(i) - list.get(i - 1));
        }
        return min;
    }

    private void treeSlipMid(TreeNode root) {
        if (root == null) return;
        treeSlipMid(root.left);
        list.add(root.val);
        treeSlipMid(root.right);
    }

    List<Integer> list;

    // 错误题解
    public int getMinimumDifference_fail(TreeNode root) {
        if (root != null) {
            if (root.left != null) {
                min = Math.min(min, -root.left.val + root.val);
                getMinimumDifference_fail(root.left);
            }
            if (root.right != null) {
                min = Math.min(min, root.right.val - root.val);
                getMinimumDifference_fail(root.right);
            }
        }
        return min;
    }

    int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        _530二叉搜索树的最小绝对差 minDiffInBST = new _530二叉搜索树的最小绝对差();
        TreeNode root = new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(6));
        System.out.println(minDiffInBST.getMinimumDifference_option(root));
    }
}