1.题目

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

示例：

  1. 输入：
  3.    1
  4.     \
  5.      3
  6.     /
  7.    2
  9. 输出：
  10. 1
  12. 解释：
  13. 最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

提示：

  • 树中至少有 2 个节点。

2.思路

本题要求二叉搜索树任意两节点差的绝对值的最小值，而我们知道二叉搜索树有个性质为二叉搜索树中序遍历得到的值序列是递增有序的，因此我们只要得到中序遍历后的值序列即能用上文提及的方法来解决。

  1. class Solution {
  2.     int pre;
  3.     int ans;
  5.     public int getMinimumDifference(TreeNode root) {
  6.         ans = Integer.MAX_VALUE;
  7.         pre = -1;
  8.         dfs(root);
  9.         return ans;
  10.     }
  12.     public void dfs(TreeNode root) {
  13.         if (root == null) {
  14.             return;
  15.         }
  16.         dfs(root.left);
  17.         if (pre == -1) {
  18.             pre = root.val;
  19.         } else {
  20.             ans = Math.min(ans, root.val - pre);
  21.             pre = root.val;
  22.         }
  23.         dfs(root.right);
  24.     }
  25. }