LC.783 ｜ 二叉搜索树节点最小距离 ｜ 树 ｜ 中序遍历有序性

输入：二叉搜索树的根节点root。

要求：计算树中任意两个不同节点值之间的最小差值。

输出：一个整数，表示最小差值。

思路：

这道题如果是一棵普通的二叉树，我们需要把所有节点值存下来，两两比较，复杂度是 O(N^2)。但因为它是二叉搜索树 (BST)，我们可以利用其特性将问题极大简化。

1. 核心转化：BST -> 有序数组
   • 二叉搜索树的中序遍历结果是一个单调递增的有序数组。
   • 在一个有序数组中，最小的差值一定出现在相邻的两个数之间。
   • 例如：[1, 4, 7, 9]。差值只可能产生在4-1,7-4,9-7之间，绝对不可能产生在9-1之间。
2. 优化空间：双指针思维
   • 我们不需要真的开辟一个数组把所有数存下来（那样空间复杂度是 O(N)）。
   • 我们在遍历过程中，只需要知道“上一个遍历到的节点值” (last或prev)是多少。
   • 当前节点值root->val减去上一个节点值last，就是当前的相邻差值。我们不断更新这个差值的最小值即可。
3. 处理细节：
   • 我们需要一个变量last来记录上一个节点的值。初始化为-1（或者一个不可能的负数），表示这是第一个节点，还没上家，不计算差值。

复杂度：

• 时间复杂度：O(N)
  • 需要中序遍历整棵树。
• 空间复杂度：O(H)
  • H 为树的高度，主要是递归栈的空间。

class Solution { public: void inorder(TreeNode* root, int& ans, int& last) { if (!root) { return; } // 1. 递归左子树 inorder(root->left, ans, last); // 2. 处理当前节点（中序位置） if (last == -1) { // 如果是第一个节点，只需更新 last，没法计算差值 last = root->val; } else { // 计算当前节点与上一个节点的差值，并更新最小值 // 因为是中序遍历，root->val 一定大于 last，所以不用 abs 也行 ans = min(abs(root->val - last), ans); // 更新 last 为当前节点，供下一次使用 last = root->val; } // 3. 递归右子树 inorder(root->right, ans, last); } int minDiffInBST(TreeNode* root) { int ans = INT_MAX; int last = -1; // 用于记录中序遍历中的“上一个”节点值 inorder(root, ans, last); return ans; } };