LeetCode530-二叉搜索树的最小绝对差

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/minimum-absolute-difference-in-bst/

中文链接：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/

题目详述

给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。

示例 :

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:

   1
    \
     3
    /
   2

输出:
1

解释:
最小绝对差为1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

注意: 树中至少有2个节点。

题目详解

因为是一颗二叉搜索树，所以对它进行中序遍历得到的结果是有序的，树中任意两节点的差的绝对值的最小值就是所有中序遍历序列相邻结点差的最小值。

方法一：迭代。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode_00530 {

    public int getMinimumDifference(TreeNode root) {
        int res = Integer.MAX_VALUE;
        Stack<TreeNode> stack = new Stack<>();
        Integer pre = null;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (pre != null) {
                res = Math.min(res, root.val - pre);
            }
            pre = root.val;
            root = root.right;
        }
        return res;
    }
}

方法二：递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode_00530 {

    public int getMinimumDifference(TreeNode root) {
        int[] pre = new int[]{-1};
        int[] res = new int[]{Integer.MAX_VALUE};
        inOrder(root, pre, res);
        return res[0];
    }

    private void inOrder(TreeNode root, int[] pre, int[] res) {
        if (root == null) {
            return;
        }
        inOrder(root.left, pre, res);
        if (pre[0] != -1) {
            res[0] = Math.min(res[0], root.val - pre[0]);
        }
        pre[0] = root.val;
        inOrder(root.right, pre, res);
    }
}

我们还可以换一种思路，不用中序遍历。对于二叉搜索树，常常可以采取传入上限和下限的方式，在递归过程中更新结果和当前的上限和下限。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_00530 {

    public int getMinimumDifference(TreeNode root) {
        int[] res = new int[]{Integer.MAX_VALUE};
        dfs(root, Integer.MIN_VALUE, Integer.MAX_VALUE, res);
        return res[0];
    }

    private void dfs(TreeNode root, int min, int max, int[] res) {
        if (root == null) {
            return;
        }
        if (min != Integer.MIN_VALUE) res[0] = Math.min(res[0], root.val - min);
        if (max != Integer.MAX_VALUE) res[0] = Math.min(res[0], max - root.val);
        dfs(root.left, min, root.val, res);
        dfs(root.right, root.val, max, res);
    }
}