題目描述

給定一個(gè)二叉搜索樹的根節(jié)點(diǎn) root，返回樹中任意兩節(jié)點(diǎn)的差的最小值。
783. 二叉搜索樹節(jié)點(diǎn)最小距離

解法1 中序遍歷

二叉搜索樹的中序遍歷是非降序排列，每次遍歷一個(gè)點(diǎn)，跟它前面的點(diǎn)比較，如果比記錄到的最小值小，更新最小值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //min用來(lái)存放最小距離，默認(rèn)值為Integer的最大值，pre用于保存上一個(gè)節(jié)點(diǎn)
    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);
        //判斷當(dāng)前節(jié)點(diǎn)與前一個(gè)節(jié)點(diǎn)的距離是否比min小，是則更新min
        if (pre != null) {
            if (Math.abs(root.val - pre.val) < min) {
                min = Math.abs(root.val - pre.val);
            }
        }
        //遍歷下個(gè)節(jié)點(diǎn)前，更新root為當(dāng)前節(jié)點(diǎn)
        pre = root;
        inorder(root.right);
    }
}