力扣第530与783题 c++（暴力，加双指针优化）附迭代版本

题目

530. 二叉搜索树的最小绝对差

783. 二叉搜索树节点最小距离

简单

思路和解题方法一（暴力）

首先定义一个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; // 返回最小差值}
};

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦 >人< 。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/155506.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！