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

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

题解：
  • 二叉搜索树中序遍历的结果，是升序数组
  • 中序遍历二叉树，每一步记录与上一步的差值，取最小值即为最终结果
思路一：

迭代

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public int getMinimumDifference1(TreeNode root){

        // 中序遍历前一个元素
        TreeNode prev = null;
        // 保存最小差值
        int minDiff = Integer.MAX_VALUE;

        Stack<TreeNode> stack = new Stack<>();

        while (!stack.isEmpty() || root != null){
            while (root != null){
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            if (prev == null)
                minDiff = Integer.MAX_VALUE;
            else
                minDiff = Math.min(root.val - prev.val, minDiff);

            prev = root;

            root = root.right;
        }

        return minDiff;
    }
思路二：

递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

   // 递归
    TreeNode prev = null;
    int minDiff = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root){
        if (root == null) return Integer.MAX_VALUE;

        // 找到左子树的最小差值
        getMinimumDifference(root.left);

        // 计算当前节点的最小差值
        int val = root.val;
        if (prev == null)
            minDiff = Integer.MAX_VALUE;
        else
            minDiff = Math.min(root.val - prev.val,minDiff);

        prev = root;

        // 找到右子树的最小差值
        getMinimumDifference(root.right);
        
        return minDiff;
    }