530. Minimum Absolute Difference in BST

/** * 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) { if (root == nullptr) return 0; else if (root->left == nullptr){ if (root->right == nullptr) return 0; else{ // only the right subtree // the first candidate of the min number! int candidate1 = getMinimumDifference(root->right); // find the second candidate TreeNode * leftmost = root->right; while (leftmost->left != nullptr) leftmost = leftmost->left; int candidate2 = std::abs(root->val - leftmost->val); return std::max(candidate1, candidate2); } } else if (root->right == nullptr){ // only the left subtree int candidate1 = getMinimumDifference(root->left); // find the second candidate TreeNode * rightmost = root->left; while (rightmost->right != nullptr) rightmost = rightmost->right; int candidate2 = std::abs(root->val - rightmost->val); return std::max(candidate1, candidate2); } else { // both left subtree and the right subtree int candidate1 = getMinimumDifference(root->right); // find the second candidate TreeNode * leftmost = root->right; while (leftmost->left != nullptr) leftmost = leftmost->left; int candidate2 = std::abs(root->val - leftmost->val); int candidate3 = getMinimumDifference(root->left); TreeNode * rightmost = root->left; while (rightmost->right != nullptr) rightmost = rightmost->right; int candidate4 = std::abs(root->val - rightmost->val); int right_max = std::max(candidate1, candidate2); int left_max = std::max(candidate3, candidate4); return std::max(left_max, right_max); } } };