53 lines
1.2 KiB
JavaScript
53 lines
1.2 KiB
JavaScript
/**
|
|
* Definition for a binary tree node.
|
|
* function TreeNode(val, left, right) {
|
|
* this.val = (val===undefined ? 0 : val)
|
|
* this.left = (left===undefined ? null : left)
|
|
* this.right = (right===undefined ? null : right)
|
|
* }
|
|
*/
|
|
/**
|
|
* @param {TreeNode} root
|
|
* @return {number}
|
|
*/
|
|
const getMinimumDifference = function (root) {
|
|
|
|
};
|
|
|
|
/*
|
|
二叉搜索树的一个重要特征就是，中序遍历的结果是一个升序序列，所以只要中序遍历整个二叉树，前一个节点和当前节点作比较的值的绝对值就可能
|
|
是这个最小的差值
|
|
*/
|
|
function f1(root) {
|
|
let prev = null; // 记录前一个节点的值
|
|
let minDiff = Infinity; // 初始化最小差值为正无穷
|
|
|
|
// 中序遍历函数
|
|
function inOrder(node) {
|
|
if (!node) return;
|
|
|
|
// 先遍历左子树
|
|
inOrder(node.left);
|
|
|
|
// 当前节点与前一个节点的差值
|
|
if (prev !== null) {
|
|
minDiff = Math.min(minDiff, Math.abs(node.val - prev));
|
|
}
|
|
|
|
// 更新前一个节点为当前节点
|
|
prev = node.val;
|
|
|
|
// 再遍历右子树
|
|
inOrder(node.right);
|
|
}
|
|
|
|
// 从根节点开始中序遍历
|
|
inOrder(root);
|
|
|
|
return minDiff;
|
|
}
|
|
|
|
/*
|
|
使用迭代实现中序遍历
|
|
*/
|