二叉搜索树节点最小距离 图解题解

给一棵 BST，任意两点差最小是多少

给定一棵二叉搜索树，也就是左小右大的那种二叉树，返回树里任意两个不同节点值之差的绝对值的最小可能值。题面这棵 root=[50,30,80,10,35,70,90]，答案是 5，来自 30 和 35 这对最接近的值。节点值互不相同、至少两个。

两两求差要比 n² 次，白费在哪

把每两个节点凑成一对求差、再挑最小，一棵 n 个节点的树有大约 n²/2 对，全比一遍是 O(n²)。这么做完全没用上 BST 的有序性：树里绝大多数点对差得很远，两个隔着好几个值的数，差不可能比它们中间夹着的相邻两数更小，比它们纯属浪费。

为什么最小差一定藏在相邻两值之间

BST 有一条硬性质：中序遍历，也就是按左子树、根、右子树的顺序访问，得到的是一串从小到大的升序值。既然值已经排成有序队列，两个数在队列里隔得越远、差只会越大；真正可能最小的差，只会出现在队列里紧挨着的两个数之间。于是问题从「两两比」缩成「把中序序列相邻两项的差各算一遍、取最小」，一趟遍历就够。

中序走一遍，pre 记前驱、ans 收最小

具体做法是一次中序 DFS，也就是顺着树一条路走到底再回头：递归进左子树，回到当前节点时结算，再递归进右子树。结算要拿当前值和它在升序序列里的前一个值作差，所以额外备一个变量 pre 记住上一个访问到的节点值。每访问一个节点就更新 ans=min(ans, 当前值−pre)，再把 pre 换成当前值。

pre 初始设成负无穷，这样第一个节点算出的差是无穷大、压不动答案，它只负责给 pre 起个头；ans 初始设成正无穷，等着被真实的差一点点顶下来。

拿 [50,30,80,10,35,70,90] 逐项收相邻差

从根 50 往左钻到 30、再到 10，10 没有左子树，成了中序第一个访问到的节点。此时 pre 还是负无穷，算出的差是无穷大，ans 不动，只把 pre 记成 10。回到 30：ans=min(∞, 30−10)=20，pre=30。转进 30 的右孩子 35：ans=min(20, 35−30)=5，pre=35，最小差头一回被压到 5。

接着回到根 50：ans=min(5, 50−35)=15 里 5 更小，ans 保持 5，pre=50。转向右子树，先到左孩子 70：ans=min(5, 70−50)=20，仍是 5；再到 80：80−70=10；最后 90：90−80=10，都没能压过 5。整条中序序列是 10、30、35、50、70、80、90，相邻差依次 20、5、15、20、10、10，最小的 5 来自 30 与 35，这就是答案。

一遍中序为什么是 O(n)，还有两处易错

每个节点只在中序里被访问一次，一次减法加一次取最小，时间 O(n)；递归吃的是调用栈，栈深随树高 h 变：均衡时约 O(log n)，塌成单链就到 O(n)，空间 O(h)。

两个地方最容易栽：pre 若初始设成 0 或某个真实值，第一个节点会算出一个假的差把答案带偏，得设成负无穷让它空转一轮；访问顺序也不能乱，一旦不是严格的左、根、右，中序序列就不再升序，只比相邻两数这套逻辑当场失效。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        def dfs(root: Optional[TreeNode]):
            if root is None:
                return
            dfs(root.left)
            nonlocal pre, ans
            ans = min(ans, root.val - pre)
            pre = root.val
            dfs(root.right)

        pre = -inf
        ans = inf
        dfs(root)
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        const int inf = 1 << 30;
        int ans = inf, pre = -inf;
        function<void(TreeNode*)> dfs = [&]( TreeNode* root ) -> void {
            if (!root) {
                return;
            }
            dfs(root->left);
            ans = min(ans, root->val - pre);
            pre = root->val;
            dfs(root->right);
        };
        dfs(root);
        return ans;
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private final int inf = 1 << 30;
    private int ans = inf;
    private int pre = -inf;

    public int minDiffInBST(TreeNode root) {
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        ans = Math.min(ans, root.val - pre);
        pre = root.val;
        dfs(root.right);
    }
}