LeetCode Minimum Absolute Difference in BST Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes. Example:

Input:
   1
    \
     3
    /
   2
Output:
1
Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.

---

求一棵二叉搜索树中任意两个节点数值之差的绝对值的最小值。 因为是BST，所以满足左子树<=根节点<=右子树。以根节点root为例，则最小的差可能有两个，一个是root减去左子树中的最大数，另一个是右子树中的最小数减去root，所以整体的最小值就是这两个最小值的最小值。 左子树中的最大数就是左子树中最右下端的叶子节点，右子树中的最小数就是右子树中最左下端的叶子节点。 然后递归的以左右孩子为根更新最小值。代码如下： [cpp] class Solution { public: int getMinimumDifference(TreeNode* root) { int l = INT_MIN, r = INT_MAX; int left_min = INT_MAX, right_min = INT_MAX; if (root->left) { TreeNode* left = root->left; while (left->right)left = left->right; left_min = min(root->val – left->val, getMinimumDifference(root->left)); } if (root->right) { TreeNode* right = root->right; while (right->left)right = right->left; right_min = min(right->val – root->val, getMinimumDifference(root->right)); } return min(left_min, right_min); } }; [/cpp] 本代码提交AC，用时19MS。 还有一种思路，因为是BST，所以其中序遍历的结果是升序的，得到有序数组之后，相邻两个数的差的最小值就是要求的结果。 实际上，我们可以不用完整求出其升序序列之后再计算差，只需要在每次中序遍历时，记住该节点的上一个节点，这样该节点的值减去上一节点的值就相当于有序数组中相邻两个数作差。 代码如下： [cpp] class Solution { private: long long m_nLast, m_nAns; void inorderTraverse(TreeNode* root) { if (!root)return; inorderTraverse(root->left); // 左 m_nAns = min(m_nAns, root->val – m_nLast); m_nLast = root->val; // 根 inorderTraverse(root->right); // 右 } public: Solution() { m_nLast = INT_MIN; m_nAns = INT_MAX; } int getMinimumDifference(TreeNode* root) { inorderTraverse(root); return m_nAns; } }; [/cpp] 本代码提交AC，用时16MS。注意因为可能出现x-INT_MIN导致int溢出，所以两个成员变量定义为long long。 参考：http://bookshadow.com/weblog/2017/02/26/leetcode-minimum-absolute-difference-in-bst/]]>