给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。
示例:
输入:
1
\
3
/
2
输出:
1
解释:
最小绝对差为 1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。
提示:
- 树中至少有 2 个节点。
- 本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> container;
int getMinimumDifference(TreeNode* root) {
dfs(root);
sort(container.begin(), container.end());
if(container.size() < 2 ){
return 0;
}
int minAbs = abs(container[0] - container[1]);
for(int i = 1;i<container.size();i++){
minAbs = min(minAbs, abs(container[i] - container[i-1]));
}
return minAbs;
}
void dfs(TreeNode* root){
if(root == NULL) return;
container.push_back(root->val);
dfs(root->left);
dfs(root->right);
}
};