题目描述

给定一个二叉搜索树的根节点 root，返回树中任意两节点的差的最小值。
783. 二叉搜索树节点最小距离

解法1 中序遍历

二叉搜索树的中序遍历是非降序排列，每次遍历一个点，跟它前面的点比较，如果比记录到的最小值小，更新最小值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //min用来存放最小距离，默认值为Integer的最大值，pre用于保存上一个节点
    int min = Integer.MAX_VALUE;
    TreeNode pre = null;

    public int minDiffInBST(TreeNode root) {
        inorder(root);
        return min;
    }
    //中序遍历
    public void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        //判断当前节点与前一个节点的距离是否比min小，是则更新min
        if (pre != null) {
            if (Math.abs(root.val - pre.val) < min) {
                min = Math.abs(root.val - pre.val);
            }
        }
        //遍历下个节点前，更新root为当前节点
        pre = root;
        inorder(root.right);
    }
}