530. Minimum Absolute Difference in BST
530. Minimum Absolute Difference in BST
🟢 🔖 树
深度优先搜索
广度优先搜索
二叉搜索树
二叉树
🔗 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, 104]
. 0 <= Node.val <= 10^5
Note: This question is the same as 783
题目大意
给你一个二叉搜索树的根节点 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;
};
相关题目
相关题目
- [532. 数组中的 k-diff 数对](https://leetcode.com/problems/k-diff-pairs-in-an-array)