Leetcode 530. Minimum Absolute Difference in BST

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

• Version 1

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int getMinimumDifference(TreeNode* root) {vector<int> values;inOrderTranverse(root, values);int min = INT_MAX;for(int i = 1; i < values.size(); i++) {int diff = values[i] - values[i - 1];if(min > diff) {min = diff;}}return min;}private:void inOrderTranverse(TreeNode* root, vector<int>& values) {if(!root) {return;}if(root->left) {inOrderTranverse(root->left, values);}values.push_back(root->val);if(root->right) {inOrderTranverse(root->right, values);}}
};

• Version 2

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int getMinimumDifference(TreeNode* root) {int min = INT_MAX;int current = -1;inOrderTranverse(root, min, current);return min;}private:void inOrderTranverse(TreeNode* root, int& min, int& current) {if(!root) {return;}if(root->left) {inOrderTranverse(root->left, min, current);}if(current != -1) {if(min > root->val - current) {min = root->val - current;}}current = root->val;if(root->right) {inOrderTranverse(root->right, min, current);}}
};

Reference

1. https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/