530 Minimum Absolute Difference in BST (Verbose)

// // Created by YUQIONG LI on 22/9/2018. // #include <iostream> #include <stack> #include <vector> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: void inorder_iterative(TreeNode * root, vector<int> & res){ if (root == nullptr) return; // This version, all nodes pushed into the stack at least once stack< pair<TreeNode *, int> > s; pair<TreeNode *, int> p = make_pair(root, 1); // int = 1: first time see. int = 2: second time see s.push(p); while(!s.empty()){ p = s.top(); s.pop(); TreeNode * curr = p.first; int tag = p.second; if (tag == 2) // second time see: we come back from the children! res.push_back(curr->val); else{ // first time seen. Operate on this if (curr->right != nullptr){ pair<TreeNode *, int> p1 = make_pair(curr->right, 1); // right node s.push(p1); } pair<TreeNode *, int> p = make_pair(curr, 2); s.push(p); if (curr->left != nullptr){ pair<TreeNode *, int> p2 = make_pair(curr->left, 1); // left node s.push(p2); } } } } int getMinimumDifference(TreeNode* root) { vector<int> res; inorder_iterative(root, res); int global_min = abs(res[1] - res[0]); for(std::vector<int>::size_type i = 2; i != res.size(); i++){ int curr_diff = abs(res[i] - res[i-1]); global_min = global_min > curr_diff? curr_diff : global_min; } return global_min; } }; int main(){ TreeNode * root = new TreeNode(1); root->right = new TreeNode(3); root->right->left = new TreeNode(2); Solution s; vector<int> res; cout << s.getMinimumDifference(root); return 0; }