LeetCode Algorithm 530. 二叉搜索树的最小绝对差

530. 二叉搜索树的最小绝对差

Ideas

前几天一直刷链表题，这道题刚看到的时候还有点懵，第一个想到的方法竟然是全排列，脑子瓦特了。

二叉树的题目基本上都得跟（前/中/后）序遍历扯点关系，一看是没注意二叉搜索树这个信息，导致一直没想明白，还是从例子中发现这是二叉搜索树的。

二叉搜索树的中序遍历是一个升序的序列，那么所有元素的最小绝对差其实就是相邻两个元素差的最小值。

然后直接默写二叉树中序遍历模板，修改一下输出逻辑部分就OK了。

Code C++

class Solution { public: int middle_order_traversal(TreeNode* node) { if (!node) { return 0; } int pre = -1, ans = INT_MAX; stack<TreeNode*> sta; TreeNode* item = node; while (!sta.empty() || item != nullptr) { if (item != nullptr) { sta.push(item); item = item->left; } else { item = sta.top(); if (pre == -1) { pre = item->val; } else { ans = min(ans, item->val - pre); pre = item->val; } sta.pop(); item = item->right; } } return ans; } int getMinimumDifference(TreeNode* root) { return middle_order_traversal(root); } };