783. Minimum Distance Between BST Nodes
1. Description
Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree.
Note: This question is the same as 530: https://leetcode.com/problems/minimum-absolute-difference-in-bst/
2. Example
Example 1:
Input: root = [4,2,6,1,3]
Output: 1
Example 2:
Input: root = [1,0,48,null,null,12,49]
Output: 1
3. Constraints
- The number of nodes in the tree is in the range [2, 100].
- 0 <= Node.val <= $10^5$
4. Solutions
My Accepted Solution
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(1)
// morris iteration
// morris iteration
class Solution {
public:
int minDiffInBST(TreeNode *i_root) {
int minDiff = INT_MAX;
for (TreeNode *currentNode = i_root, *prevNode = nullptr; currentNode;) {
if (currentNode->left == nullptr) {
getMinDiff(currentNode->val, minDiff);
currentNode = currentNode->right;
} else {
prevNode = currentNode->left;
while (prevNode->right && prevNode->right != currentNode)
prevNode = prevNode->right;
if (prevNode->right == nullptr) {
prevNode->right = currentNode;
currentNode = currentNode->left;
} else {
prevNode->right = nullptr;
getMinDiff(currentNode->val, minDiff);
currentNode = currentNode->right;
}
}
}
return minDiff;
}
private:
int prevValue = -100000; // the value range is [0, 100000]
void getMinDiff(int nodeValue, int &m_minDiff) {
m_minDiff = min(nodeValue - prevValue, m_minDiff);
prevValue = nodeValue;
}
};