curTain

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

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

给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。

示例:

输入:

   1
    \
     3
    /
   2

输出:
1

解释:
最小绝对差为 1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。

解题思路

由题可知树为排序二叉树,排序二叉树的特性是:中序遍历为升序

存下上一个节点的值,递归到下一个节点时,用下一个节点的值减上一个节点的值,依次递归,取最小值即可

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var getMinimumDifference = function(root) {
let ans = Number.MAX_SAFE_INTEGER, pre = -1;
const dfs = (root) => {
if (root === null) {
return;
}
dfs(root.left);
if (pre == -1) {
pre = root.val;
} else {
ans = Math.min(ans, root.val - pre);
pre = root.val;
}
dfs(root.right);
}
dfs(root);
return ans;
};

 评论