LeetCode783-二叉搜索树的最小距离和

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/minimum-distance-between-bst-nodes/

中文链接：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/

题目详述

给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。

示例：

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

解释:
注意，root是树结点对象(TreeNode object)，而不是数组。

给定的树 [4,2,6,1,3,null,null] 可表示为下图:

      4
    /   \
  2      6
 / \    
1   3

最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。
注意：

  1. 二叉树的大小范围在 2 到 100。
  2. 二叉树总是有效的，每个节点的值都是整数，且不重复。

题目详解

二叉搜索树任意两结点的差的最小值必定存在于中序遍历相邻结点之间。实际上，本题与 LeetCode530-二叉搜索树的最小绝对差 的解答是一致的。

迭代：

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

    public int minDiffInBST(TreeNode root) {
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode pre = null;
        int res = Integer.MAX_VALUE;
        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.val);
            }
            pre = root;
            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_00783 {

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

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