各位题友大家好！今天是 @负雪明烛 坚持日更的第 79 天。今天力扣上的每日一题是「783. 二叉搜索树节点最小距离」。

解题思路

今天题目重点：
1. 二叉搜索树（BST）
2. 任意两个不同节点

遇到二叉搜索树，立刻想到这句话：「二叉搜索树（BST）的中序遍历是有序的」。这是解决所有二叉搜索树问题的关键。

要求 BST 的任意两个不同节点之间的最小差值，也就是相当于求 BST 中序遍历得到的有序序列中所有相邻节点之间的最小差值。

分享二叉树遍历的经验：先序、中序、后序遍历方式的区别在于把「执行操作」放在两个递归函数的位置。伪代码在下面。

先序遍历：

def dfs(root):
 if not root:
     return
 执行操作
 dfs(root.left)
 dfs(root.right)

中序遍历：

def dfs(root):
 if not root:
     return
 dfs(root.left)
 执行操作
 dfs(root.right)

后序遍历：

def dfs(root):
 if not root:
     return
 dfs(root.left)
 dfs(root.right)
 执行操作

本题是使用了中序遍历，所以把「执行操作」这一步改成自己想要的代码。用本题作为示例。

于是有了下面两种写法。

方法一：数组保存中序遍历结果

这个方法是最直观的，也不容易出错的。

先中序遍历，把结果放在数组中；
2. 然后对数组中的相邻元素求差，得到所有差值的最小值。

对应的代码如下，二叉树的各种遍历方式是基本功，务必要掌握。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def minDiffInBST(self, root):
        self.vals = []
        self.inOrder(root)
        return min([self.vals[i + 1] - self.vals[i] for i in xrange(len(self.vals) - 1)])
    def inOrder(self, root):
        if not root:
            return 
        self.inOrder(root.left)
        self.vals.append(root.val)
        self.inOrder(root.right)

时间复杂度：$O(N)$，因为每个节点只访问了一次；
空间复杂度：$O(N)$，因为需要数组保存二叉树的每个节点值。

方法二：只保存上个节点

在方法一中，我们保存了整个中序遍历数组，比较浪费空间。

其实我们只需要知道，在中序遍历的时候的两个被依次访问的节点。注意，这里说的不是 BST 的相邻节点，因为在中序遍历时，在访问根节点前，上一个被访问的节点是其左子树的最右下角的节点。如下图所示，访问节点4 之前，访问的是节点3。

所以，我们只需要一个变量 prev 保存在中序遍历时，上一次被访问的节点。因为在中序遍历的过程中，节点的值是依次递增的，因此求差值的方式应该是 root.val - prev.val ，对该值取最小，就是 BST 任意两个节点的最小差值。

这里需要注意一个细节：中序遍历时的第一个节点，并没有 prev 节点。此时应该怎么办？其实就是不求第一个节点和上个节点的差值就行。可以把 prev 初始化为 None，遍历时对 prev 进行一个判断，如果 prev 为 None，说明当前遍历的是中序遍历的第一个节点，跳过求差值；此后的遍历中，在每次求完 diff 之后，把 prev 设置为当前遍历的节点。

代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def minDiffInBST(self, root):
        self.prev = None
        self.minDiff = 10e6
        self.inOrder(root)
        return self.minDiff
    def inOrder(self, root):
        if not root:
            return 
        self.inOrder(root.left)
        if self.prev:
            self.minDiff = min(root.val - self.prev.val, self.minDiff)
        self.prev = root
        self.inOrder(root.right)

时间复杂度：$O(N)$，因为每个节点只访问了一次；
空间复杂度：$O(N)$，因为递归用了系统栈。
刷题心得

二叉树的多种遍历方式必须要掌握呀。另外建议刚开始刷题的朋友，不妨从二叉树上手。

参考资料：无。

OK，以上就是 @负雪明烛写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！

算法每日一题题解

【每日一题】783. 二叉搜索树节点最小距离

解题思路

方法一：数组保存中序遍历结果

方法二：只保存上个节点

刷题心得