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

这道题到底在问什么

输入

root=[50,30,80,10,35,70,90]

输出

5

先想最直接的笨办法

中序序列是 10、30、35、50、70、80、90，确实从小到大。相邻差依次是 20、5、15、20、10、10，最小的是 30 和 35 之间的 5，这就是答案。我们没有两两枚举所有节点对，只靠 BST 中序有序、比了相邻几对就锁定了结果。（动画第 25 步）

最优解：一步一步想明白

1. 3记住这套「中序升序、只比相邻、pre 记前驱、ans 取最小」，下面每帧都在套它。
2. 4从根 50 向左下探这是一棵二叉搜索树。它的中序遍历（左、根、右）得到的是从小到大的有序序列，所以任意两点的最小差，必定落在排序后相邻的两个值之间。我们从根 50 出发，先一路向左，去找最小的那个节点。
3. 5去往 30还轮不到 50，因为它的左子树没走完。沿左边往下，走到左孩子 30，继续找更小、更靠左的节点。
4. 6去往 10还轮不到 30，因为它的左子树没走完。沿左边往下，走到左孩子 10，继续找更小、更靠左的节点。
5. 7记入序列 10中序讲究左、根、右。10 的左子树已经全部走完，现在轮到它自己，把 10 记进中序序列。它就是当前升序序列里最新的一个。
6. 8pre = 1010 是中序序列的第一个，也就是整棵树里最小的值。它前面没有前驱，做不了差，我们只把 pre 记成 10，等下一个节点来和它比。
7. 9记入序列 30中序讲究左、根、右。30 的左子树已经全部走完，现在轮到它自己，把 30 记进中序序列。它就是当前升序序列里最新的一个。
8. 10差 20 ← 刷新轮到结算：用当前值 30 减去前驱 10，相邻差是 20。它比之前的最小差 无穷大 还小，把 ans 刷新成 20。 然后把 pre 更新成 30，继续往后走。
9. 11去往 3530 已经访问并结算完了，标成蓝色。按中序规矩，接着去它的右子树，走向右孩子 35，那边的值都比 30 大。
10. 12记入序列 35中序讲究左、根、右。35 的左子树已经全部走完，现在轮到它自己，把 35 记进中序序列。它就是当前升序序列里最新的一个。
11. 13差 5 ← 刷新轮到结算：用当前值 35 减去前驱 30，相邻差是 5。它比之前的最小差 20 还小，把 ans 刷新成 5。 然后把 pre 更新成 35，继续往后走。
12. 14记入序列 50中序讲究左、根、右。50 的左子树已经全部走完，现在轮到它自己，把 50 记进中序序列。它就是当前升序序列里最新的一个。
13. 15差 15轮到结算：用当前值 50 减去前驱 35，相邻差是 15。它没比当前最小差 5 更小，ans 保持 5 不变。 然后把 pre 更新成 50，继续往后走。
14. 16去往 8050 已经访问并结算完了，标成蓝色。按中序规矩，接着去它的右子树，走向右孩子 80，那边的值都比 50 大。
15. 17去往 70还轮不到 80，因为它的左子树没走完。沿左边往下，走到左孩子 70，继续找更小、更靠左的节点。
16. 18记入序列 70中序讲究左、根、右。70 的左子树已经全部走完，现在轮到它自己，把 70 记进中序序列。它就是当前升序序列里最新的一个。
17. 19差 20轮到结算：用当前值 70 减去前驱 50，相邻差是 20。它没比当前最小差 5 更小，ans 保持 5 不变。 然后把 pre 更新成 70，继续往后走。
18. 20记入序列 80中序讲究左、根、右。80 的左子树已经全部走完，现在轮到它自己，把 80 记进中序序列。它就是当前升序序列里最新的一个。
19. 21差 10轮到结算：用当前值 80 减去前驱 70，相邻差是 10。它没比当前最小差 5 更小，ans 保持 5 不变。 然后把 pre 更新成 80，继续往后走。
20. 22去往 9080 已经访问并结算完了，标成蓝色。按中序规矩，接着去它的右子树，走向右孩子 90，那边的值都比 80 大。
21. 23记入序列 90中序讲究左、根、右。90 的左子树已经全部走完，现在轮到它自己，把 90 记进中序序列。它就是当前升序序列里最新的一个。
22. 24差 10轮到结算：用当前值 90 减去前驱 80，相邻差是 10。它没比当前最小差 5 更小，ans 保持 5 不变。 然后把 pre 更新成 90，继续往后走。
23. 25最小差 = 5（30 与 35）中序序列是 10、30、35、50、70、80、90，确实从小到大。相邻差依次是 20、5、15、20、10、10，最小的是 30 和 35 之间的 5，这就是答案。我们没有两两枚举所有节点对，只靠 BST 中序有序、比了相邻几对就锁定了结果。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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);
    }
}

复杂度

面试官可能追问