二叉搜索树节点最小距离

力扣 783. 二叉搜索树节点最小距离

题目说明

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

注意：本题与 530：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/ 相同

提示：
- 树中节点数目在范围 [2, 100] 内
- 0 <= Node.val <= 105

示例

例1

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

例2

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

笔者理解

此题是一道二叉树算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题就是针对于二叉搜索树的性质的一次运用，二叉搜索树的中序遍历是有序的，而所有节点的最小差值又必定等于两两相近之数之差，所以我们可以在对二叉搜索树进行中序遍历中将最小差值求出来，让我们来看看具体如何实现的吧。

实现

class Solution {
    // 标记上一个节点的值
    int pre = -1;
    int result = Integer.MAX_VALUE;

    public int minDiffInBST(TreeNode root) {
        List<Integer> tree = new ArrayList();

        // 中序遍历二叉搜索树，并在途中两两比较取最小差值
        inOrder(root, tree);

        return result;
    }

    public void inOrder(TreeNode root, List<Integer> tree) {
        if (root == null) {
            return;
        }
        inOrder(root.left, tree);

        if (pre != -1) {
            result = Math.min(result, root.val - pre);
        }
        pre = root.val;

        inOrder(root.right, tree);
    }
}