leetcode 530 二叉搜索树的最小绝对差
2023-09-27 14:29:24 时间
二叉搜索树的最小绝对差
提高的二叉搜索树,直接中序遍历就是从小到达的数组。做两个数值的差,找最小的
/**
* Definition for a binary tree node.
* 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:
int pre_val = INT_MIN , diff_val = INT_MAX;
void min_diff(TreeNode* cur)
{
if(cur==nullptr) return ;
min_diff(cur->left);
if(pre_val != -1 && ( cur->val - pre_val ) < diff_val) diff_val = cur->val - pre_val;
pre_val = cur->val;
min_diff(cur->right);
}
int getMinimumDifference(TreeNode* root) {
if(root==nullptr) return 0;
min_diff(root);
return diff_val;
}
};
二刷
/**
* Definition for a binary tree node.
* 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:
double result = INT_MAX;
TreeNode* pre = nullptr;
void trak_back(TreeNode* cur)
{
if( cur == nullptr ) return;
trak_back(cur->left);
if(pre != nullptr && cur->val - pre->val < result )
result = cur->val - pre->val;
pre = cur;
trak_back(cur->right);
}
int getMinimumDifference(TreeNode* root) {
if(root == nullptr) return 0;
trak_back(root);
return result;
}
};
相关文章
- Leetcode: Minimum Height Trees
- Leetcode: Reverse Bits
- Leetcode: Climbing Stairs
- JS Leetcode 74. 搜索二维矩阵题解分析,二分法与坐标轴法
- JS leetcode 删除排序数组中的重复项 题解分析
- JS leetcode 搜索插入位置 题解分析
- [LeetCode] Flatten Binary Tree to Linked List
- [LeetCode]1437. 是否所有 1 都至少相隔 k 个元素
- LeetCode 676. 实现一个魔法字典
- LeetCode搜索二叉树的练习
- 109、【树与二叉树】leetcode ——701. 二叉搜索树中的插入操作:递归法+双指针迭代法(C++版本)
- 60、【数组】leetcode——904. 水果成篮-滑动窗口:最大窗口(C++版本)
- 【LeetCode-面试算法经典-Java实现】【05-Longest Palindromic Substring(最大回文字符串)】
- LeetCode 35. 搜索插入位置
- [LeetCode] 1305. All Elements in Two Binary Search Trees 两棵二叉搜索树中的所有元素
- [LeetCode] 983. Minimum Cost For Tickets 最低票价
- [LeetCode] 980. Unique Paths III 不同的路径之三
- [LeetCode] 938. Range Sum of BST 二叉搜索树的区间和
- [LeetCode] 428. Serialize and Deserialize N-ary Tree N叉搜索树的序列化和去序列化
- [LeetCode] Binary Search 二分搜索法
- [LeetCode] Search in a Binary Search Tree 二叉搜索树中搜索
- [LeetCode] 426. Convert Binary Search Tree to Sorted Doubly Linked List 将二叉搜索树转为有序双向链表
- [LeetCode] Two Sum IV - Input is a BST 两数之和之四 - 输入是二叉搜索树
- LeetCode Binary Search Summary 二分搜索法小结
- [LeetCode] Teemo Attacking 提莫攻击
- [LeetCode] 491. Increasing Subsequences 递增子序列
- [LeetCode] 255. Verify Preorder Sequence in Binary Search Tree 验证二叉搜索树的先序序列
- [LeetCode] 333. Largest BST Subtree 最大的二分搜索子树
- [LeetCode] 287. Find the Duplicate Number 寻找重复数
- [LeetCode] 35. Search Insert Position 搜索插入位置
- [LeetCode] 33. Search in Rotated Sorted Array 在旋转有序数组中搜索
- [LeetCode] Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树
- [LeetCode] 66. Plus One 加一运算
- leetcode 530. Minimum Absolute Difference in BST二叉搜索树的最小绝对差 (简单)
- leetcode 79. Word Search 单词搜索
- leetcode 75. Sort Colors 颜色分类
- leetcode算法108.将有序数组转换为二叉搜索树