783. Minimum Distance Between BST Nodes

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

题目

Given the root of a Binary Search Tree (BST), return the minimum 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, 100].
• 0 <= Node.val <= 10^5

Note: This question is the same as 530

题目大意

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

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

解题思路

中序遍历会有序地遍历二叉搜索树的节点，只需要在遍历过程中比较最小差值即可。

代码

/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
	let diff = Number.MAX_SAFE_INTEGER;
	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;
};

相关题目

相关题目

• 94. 二叉树的中序遍历

- [94. 二叉树的中序遍历](./0094.md)