categories: [Blog,Algorithm]

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

难度简单233
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

示例：
输入：

1
\
3
/
2

输出：
1

解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。


提示：

  • 树中至少有 2 个节点。
  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.         int pre;
  12.         int ans;
  14.     public int getMinimumDifference(TreeNode root) {
  15.         ans = Integer.MAX_VALUE;
  16.         pre = -1;
  17.         dfs(root);
  18.         return ans;
  19.     }
  21.     public void dfs(TreeNode root) {
  22.         if (root == null) {
  23.             return;
  24.         }
  25.         dfs(root.left);//左
  27.         if (pre == -1) {
  28.             pre = root.val;
  29.         } else {
  30.             ans = Math.min(ans, root.val - pre);
  31.             pre = root.val;
  32.         }
  34.         dfs(root.right);//右
  35.     }
  37. }

解析
中序遍历
思路与算法
考虑对升序数组 a 求任意两个元素之差的绝对值的最小值，答案一定为相邻两个元素之差的最小值，即
ans= min{a[i+1]−a[i]}.
其中 n 为数组 a 的长度。其他任意间隔距离大于等于 2 的下标对 (i,j) 的元素之差一定大于下标对 (i,i+1) 的元素之差，故不需要再被考虑。
回到本题，本题要求二叉搜索树任意两节点差的绝对值的最小值，而我们知道二叉搜索树有个性质为二叉搜索树中序遍历得到的值序列是递增有序的，因此我们只要得到中序遍历后的值序列即能用上文提及的方法来解决。
朴素的方法是经过一次中序遍历将值保存在一个数组中再进行遍历求解，我们也可以在中序遍历的过程中用
pre 变量保存前驱节点的值，这样即能边遍历边更新答案，不再需要显式创建数组来保存，需要注意的是
pre 的初始值需要设置成任意负数标记开头，下文代码中设置为 −1。