二叉搜索树节点最小距离（783）

题目

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

注意：本题与 530.二叉搜索树的最小绝对差 (opens new window) 相同

示例

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

输入：root = [1,0,48,null,null,12,49] 输出：1

提示

• 树中节点数目在范围 [2, 100] 内
• 0 <= Node.val <= 105

算法

排序

先遍历出树中所有值，保存在数组values中，然后由小至大地排序数组values，然后相邻数字两两求差，使用min保存这些差值中的最小值，最后结果返回min

const minDiffInBST = root => {
	let values = [];
	function BST(node) {
		if (node) {
			values.push(node.val);
			if (node.left) BST(node.left);
			if (node.right) BST(node.right);
		}
	}
	BST(root);
	let min = Infinity;
	values.sort((a, b) => a - b);
	for (let i = 1; i < values.length; i++) {
		min = Math.min(min, values[i] - values[i - 1]);
	}
	return min;
};

中序遍历

因为二叉搜索树中序遍历得到的值序列是递增有序的，所以我们使用中序遍历遍历这个二叉搜索树，用变量pre保存当前节点node的前序节点，在遍历的同时求差，使用变量min保存这个过程中的最小值，最后结果返回min

const minDiffInBST = root => {
	let min = Infinity,
		pre = -1;
	function BST(node) {
		if (!node) return;
		BST(node.left);
		if (pre !== -1) min = Math.min(min, node.val - pre);
		pre = node.val;
		BST(node.right);
	}
	BST(root);
	return min;
};