本文主要是介绍力扣第530与783题 c++（暴力，加双指针优化） 附迭代版本，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
530. 二叉搜索树的最小绝对差
783. 二叉搜索树节点最小距离
简单
相关标签
树 深度优先搜索 二叉搜索树 二叉树
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
简单
相关标签
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3] 输出：1
示例 2：
输入：root = [1,0,48,null,null,12,49] 输出：1
提示：
- 树中节点的数目范围是
[2, 104] 0 <= Node.val <= 105
注意：本题与 783 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 相同
思路和解题方法一 （暴力）
- 首先定义一个
vector<int>类型的数组vec，用于存储二叉搜索树的中序遍历结果。- 使用递归的方式进行中序遍历：
- 如果当前节点为空，直接返回。
- 遍历左子树。
- 将当前节点的值加入到
vec中。- 遍历右子树。
- 清空
vec，并调用中序遍历函数traversal将二叉搜索树的节点按照升序存储到vec中。- 如果
vec的大小小于2，说明节点数量不足以计算差值，返回0。- 初始化一个最小差值
ans为INT_MAX。- 遍历
vec，从第二个元素开始，计算当前元素与前一个元素的差值，并更新ans为较小的差值。- 返回最小差值
ans。
复杂度
时间复杂度:
O(n)
时间复杂度：O(n)，其中 n 为二叉搜索树节点的个数。每个节点在中序遍历中都会被访问一次且只会被访问一次，因此总时间复杂度为 O(n)。
空间复杂度
O(n)
空间复杂度：O(n)。递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到 O(n) 级别。
c++ 代码（暴力）
class Solution {
public:vector<int> vec; // 存储二叉搜索树中序遍历的结果// 中序遍历函数，将节点值按照升序存储到vec中void traversal(TreeNode *root){if(root == NULL) return ;// 中序遍历左子树traversal(root->left);// 将当前节点值加入vecvec.push_back(root->val);// 中序遍历右子树traversal(root->right);}// 计算二叉搜索树的最小差值int getMinimumDifference(TreeNode* root) {vec.clear(); // 清空vectraversal(root); // 进行中序遍历if(vec.size() < 2) return 0; // 如果节点数量小于2，返回0int ans = INT_MAX; // 初始最小差值为INT_MAXfor(int i = 1; i < vec.size(); i++) // 遍历vec，找到最小差值{ans = min(ans, vec[i] - vec[i-1]);}return ans;}
};
思路和解题方法二 （双指针）
- 首先设置一个初始最小差值为INT_MAX，表示无穷大。
- 使用中序遍历（左-根-右）遍历二叉搜索树。
- 在遍历过程中，每次访问到一个节点时，计算当前节点与前一个节点值的差值，并更新最小差值ans。
- 更新前一个节点pre为当前节点，以便进行下一个节点的差值计算。
- 最后返回最小差值ans。
复杂度
时间复杂度:
O(n)
时间复杂度：O(n)，其中 n 为二叉搜索树节点的个数。每个节点在中序遍历中都会被访问一次且只会被访问一次，因此总时间复杂度为 O(n)。
空间复杂度
O(n)
空间复杂度：O(n)。递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到 O(n) 级别。
c++ 代码（双指针）
class Solution {
public:// 最小差值int ans = INT_MAX;// 前一个访问的节点TreeNode* pre = NULL;// 中序遍历函数void traversal(TreeNode *root){// 递归结束条件，遍历到空节点if(root == NULL) return ;// 中序遍历左子树traversal(root->left);// 计算当前节点与前一个节点的差值，并更新最小差值if(pre != NULL) ans = min(ans, root->val - pre->val);// 更新前一个节点为当前节点pre = root;// 中序遍历右子树traversal(root->right);}// 计算二叉搜索树的最小差值int getMinimumDifference(TreeNode* root) {// 进行中序遍历，计算最小差值traversal(root);// 返回最小差值return ans;}
};c++迭代版本
- 首先定义一个
stack<TreeNode*>类型的栈st，用于存储二叉搜索树中的节点。- 初始化当前节点指针
cur为根节点，前一个访问的节点指针pre为空，最小差值result为INT_MAX。- 当
cur不为空或者栈不为空时，进入循环：
- 如果
cur不为空，将cur指向的节点入栈，并将cur指向其左子节点。- 如果
cur为空，说明已经到达某个节点的左子树的末尾，此时需要弹出栈顶元素，并判断是否有前一个访问的节点，如果有，则更新最小差值result为当前节点与前一个节点值的差的最小值。接着将pre指向当前节点，将cur指向其右子节点。- 循环结束后，返回最小差值
result。
class Solution {
public:int getMinimumDifference(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root; // 定义当前节点指针cur并初始化为根节点TreeNode* pre = NULL; // 前一个访问的节点指针pre为空int result = INT_MAX; // 初始最小差值为INT_MAXwhile (cur != NULL || !st.empty()) { // 当cur不为空或者栈不为空时，进入循环if (cur != NULL) { // 如果cur不为空st.push(cur); // 将当前节点入栈cur = cur->left; // 将当前节点指向其左子节点} else { // 如果cur为空，说明已经到达某个节点的左子树的末尾，需要弹出栈顶元素cur = st.top();st.pop();if (pre != NULL) { // 如果存在前一个访问的节点result = min(result, cur->val - pre->val); // 更新最小差值为当前节点与前一个节点值的差的最小值}pre = cur; // 将pre指向当前节点cur = cur->right; // 将当前节点指向其右子节点}}return result; // 返回最小差值}
};
觉得有用的话可以点点赞，支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。
这篇关于力扣第530与783题 c++（暴力，加双指针优化） 附迭代版本的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
