783. 二叉搜索树节点最小距离
783. 二叉搜索树节点最小距离
🟢 🔖 树
深度优先搜索
广度优先搜索
二叉搜索树
二叉树
🔗 力扣
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 | 二叉树的中序遍历 | [✓] | 栈 树 深度优先搜索 1+ |