leetcode 530 二叉搜索树的最小绝对值
程序员文章站
2022-04-24 20:07:56
...
题目:https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/
思路一:
分析;由于二叉搜索树的特性,右子树方面:2>3>1。其绝对值最小值在3-1和2-1 之间产生,而左子树:1>4>5,绝对值最小值在1-4和4-5之间 产生,所以,根据中序遍历的顺序,将中序遍历的结果放进数组,然后前面的值减去后 面的,得到差值的最小值。
步骤:
中序遍历将节点放进数组里面;
从数组开头,相邻位置相减,取差值的最小值作为返回值
class Solution {
public:
vector<int>vec;
vector<int> inorder(TreeNode* root)
{
if(root==NULL)
return vec;
if(root->left)
inorder(root->left);
vec.push_back(root->val);
if(root->right)
inorder(root->right);
return vec;
}
int getMinimumDifference(TreeNode* root) {
vector<int>vec=inorder(root);
int len=vec.size();
int nums=abs(vec[0]-vec[1]);
if(len==2)
return nums;
for(int i=1;i<len-1;i++)
{
int res=abs(vec[i]-vec[i+1]);
if(res<nums)
nums=res;
}
return nums;
}
};
思路二:递归优化
分析:不用将节点的值存在数组里面,在中序遍历的时候直接得到差值的绝对值,关键在于如何将上一个节点保存下来:用一个指针将访问到的节点保存下来
本代码中 用一个pre节点记录一下cur节点的前一个节点
class Solution {
public:
int mixnum=INT_MAX;
TreeNode*pre;
void inorder(TreeNode* root)
{
if(root==NULL)
return ;
inorder(root->left);
if(pre!=NULL)
{
mixnum=min(mixnum,root->val-pre->val);
}
pre=root;//将前一个节点保存下来
inorder(root->right);
}
int getMinimumDifference(TreeNode* root) {
inorder(root);
return mixnum;;
}
};
思路三:迭代法:
分析: 中序遍历的迭代操作(参考前面的博客)
int getMinimumDifference(TreeNode* root) {
stack<TreeNode*>stk;
int result=INT_MAX;
TreeNode* cur = root;
TreeNode*pre=NULL;
while(cur!=NULL||!stk.empty())
{
if(cur!=NULL)
{
stk.push(cur);//将访问到的节点入栈
cur=cur->left;
}
else
{
cur=stk.top();
stk.pop();
if(pre!=NULL)
{
result=min(result,cur->val-pre->val);
}
pre=cur;
cur=cur->right;
}
}
return result;
}
下一篇: 亚马逊用人工智能系统打击虚假评论
推荐阅读
-
LeetCode 426. 将二叉搜索树转化为排序的双向链表(BST中序循环遍历)
-
leetcode算法练习——不同的二叉搜索树
-
leetcode算法练习——不同的二叉搜索树
-
leetcode 235. 二叉搜索树的最近公共祖先
-
【Leetcode刷题篇】leetcode235 二叉搜索树的最近公共祖先
-
LeetCode 235--二叉搜索树的最近公共祖先 ( Lowest Common Ancestor of a Binary Search Tree ) ( C语言版 )
-
Leetcode 1305:两棵二叉搜索树中的所有元素(超详细的解法!!!)
-
Leetcode 230.二叉搜索树中第k小的元素
-
LeetCode刷题实战96:不同的二叉搜索树
-
【leetcode 简单】第二十七题 二叉树的最小深度