javascript - 如何在javascript中获取两个值或节点之间的差异
问题描述
我正在尝试解决这个问题。我没有得到预期的输出
给定具有根节点 root 的二叉搜索树 (BST),返回树中任意两个不同节点的值之间的最小差值。
例子 :
输入:
root = [4,2,6,1,3,null,null]
输出:
1
解释:
请注意,root 是 TreeNode 对象,而不是数组。
给定的树 [4,2,6,1,3,null,null] 由下图表示:
4
/ \
2 6
/ \
1 3
虽然这棵树的最小差异为 1,但它发生在节点 1 和节点 2 之间,也发生在节点 3 和节点 2 之间。
我试过这样
var minDiffInBST = function (root) {
let min = Number.MAX_VALUE
const getMin = (node) => {
if (node.left && node.right) {
console.log('both')
return Math.min(node.val - node.left.val, node.right.val - node.val)
} else if (node.right) {
console.log('right')
return node.right.val - node.val
} else if (node.left) {
console.log('left')
return node.val - node.left.val
} else {
return Number.MAX_VALUE
}
}
const preOrder = (root) => {
if (!root) {
return 0;
}
let x = getMin(root)
if (x < min)
min = x
preOrder(root.left)
preOrder(root.right)
}
preOrder(root)
return min
};
console.log(minDiffInBST({
"val": 90,
"left": {
"val": 69,
"left": {"val": 49, "left": null, "right": {"val": 52, "left": null, "right": null}},
"right": {"val": 89, "left": null, "right": null}
},
"right": null
}
))
获取输出3
预期输出 1
我的问题来自这里 https://leetcode.com/problems/minimum-distance-between-bst-nodes/
解决方案
除了 Paul Nikonowicz 评论之外,这里是我在 C++ 中的实现,使用中序遍历来获取 BST 的排序向量,然后对其进行迭代,将每个结果值与向量的最大值进行比较
#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
vector<int> toCompare = {};
/* find min diff pair of our inorder derived vector*/
int find_min(vector <int> const& a) {
int diff = *std::max_element(a.begin(), a.end());
for (int i = 0; i < a.size()-1; i++)
if (a.at(i + 1) - a.at(i) < diff) {
diff = a.at(i + 1) - a.at(i);
}
return diff;
}
int minDiffInBST(TreeNode* root) {
if (root == NULL) {
return 0;
};
/* In order traversal */
minDiffInBST(root->left);
/* Storing in vector/list */
toCompare.push_back(root->val);
minDiffInBST(root->right);
return find_min(toCompare);
};
};
int main() {
struct TreeNode* root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(6);
root->left->left = new TreeNode(3);
Solution myObj;
cout << myObj.minDiffInBST(root);
return 0;
推荐阅读
- python - 我们可以编写python自动化代码来每次打开不同的url,修改以前的url吗?
- r - 如何在 Pycharm 中绘制 R 数据?
- vue.js - 修改vue js中的复选框行为
- javascript - Highcharts 时间线,gridLine 问题背后的标记
- javascript - 寻找没有增强现实的自然特征检测库
- java - 关于如何比较均匀地划分列表
- python - 为什么转换进入数据集而不是 Pytorch 中的 NN 本身?
- python - 在 ForeignKey 中创建或获取默认对象
- javascript - 想要在第一个语句完成执行后重定向反应
- vagrant - 初始化 Fabric CA 服务器时出错,go-sqlite3 需要 cgo 才能工作