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

🟢   🔖  树 深度优先搜索 广度优先搜索 二叉搜索树 二叉树  🔗 力扣 LeetCode

题目

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

Input: root = [4,2,6,1,3]

Output: 1

Example 2:

Input: root = [1,0,48,null,null,12,49]

Output: 1

Constraints:

• The number of nodes in the tree is in the range [2, 10^4].
• 0 <= Node.val <= 10^5

Note: This question is the same as 783

题目大意

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

解题思路

思路一：中序遍历

• 因为题目给的是一个二叉搜索树，二叉搜索树的特点是，中序遍历二叉搜索树得到的数组是有序递增的；
• 因此可以中序遍历二叉搜索树的节点，将节点的值存入一个数组中；
• 然后再依次比较数组中相邻两个值，求出最小的绝对值差值。

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。
• 空间复杂度：O(n)，使用了一个数组来存放中序遍历二叉树后得到的值。

---

思路二：优化版中序遍历

可以优化思路一的空间复杂度，在遍历过程中求最小的绝对值差值

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。
• 空间复杂度：O(1)

代码

中序遍历

/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
	// 中序遍历
	const traverse = (node) => {
		if (!node) return [];
		const left = traverse(node.left);
		const right = traverse(node.right);
		return [...left, node.val, ...right];
	};
	const arr = traverse(root);

	let res = Infinity;

	// 依次比较相邻的两个值，得出最小绝对值差值
	for (let i = 1; i < arr.length; i++) {
		res = Math.min(res, arr[i] - arr[i - 1]);
	}

	return res;
};

优化版中序遍历

/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
	let diff = Infinity;
	let prev = null;
	const traverse = (root) => {
		if (!root) return null;
		traverse(root.left);
		if (prev) {
			diff = Math.min(diff, root.val - prev.val);
		}
		prev = root;
		traverse(root.right);
	};
	traverse(root);
	return diff;
};

相关题目

题号	标题	题解	标签	难度
532	数组中的 k-diff 数对		数组 哈希表 双指针 2+