首页 > 代码库 > [leetcode-530-Minimum Absolute Difference in BST]
[leetcode-530-Minimum Absolute Difference in BST]
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
Example:
Input:
1
\
3
/
2
Output:
1
Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
思路：
中序遍历能得到有序数列，而且最小差一定出现在相邻元素。
void zhongxubianli(TreeNode* root, vector<int>& tree) { if (root!=NULL) { zhongxubianli(root->left, tree); tree.push_back(root->val); zhongxubianli(root->right, tree); } } int getMinimumDifference(TreeNode* root) { vector<int>tree; zhongxubianli(root, tree); int ret = 100000; for (int i = 1; i < tree.size();i++) { ret = min(ret, tree[i] - tree[i - 1]); } return ret; }
void zhongxubianli(TreeNode* root, int& ret,int& temp) { if (root!=NULL) { zhongxubianli(root->left, ret,temp); if(temp>=0)ret = min(ret, root->val - temp); temp = root->val; zhongxubianli(root->right, ret,temp); } } int getMinimumDifference(TreeNode* root) { int ret = 100000,temp = -1; zhongxubianli(root, ret,temp); return ret; }
[leetcode-530-Minimum Absolute Difference in BST]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。