算法第十九天-二叉搜索树节点最小距离

发布时间:2024年01月15日

二叉搜索树节点最小距离

题目要求

解题思路

今天题目重点:
1.二叉搜索树(BST)
2.任意两个不同节点
遇到二叉搜索树,立即想到这句话:[二叉搜索树(BST)的中序遍历是有序的]。这是解决所有二叉搜索树问题的关键。

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

分享二叉树遍历的经验:先序、中序、后序遍历方式的区别在于把[执行操作]放在两个递归的位置。
伪代码如下:
1.先序遍历

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

2.中序遍历

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

3.后序遍历

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

本题使用了中序遍历,所以把[执行操作]这一步改成自己想要的代码。

方法一、数组保存中序遍历结果
这个方法最直观,也最不容易出错。
1.先中序遍历,把结果放在数组中;然后对数组中的相邻元素求差,得到所有差值的最小值。

方法二、只保存上个节点
在方法一中,我们保存了整个中序遍历数组,比较浪费空间。
其实我们只需要知道,在中序遍历的时候的两个被依次访问的节点。注意,这里说的不是BST的相邻节点,因为在中序遍历时,在访问根节点前,上一个被访问的节点时其左子树的最优下的节点。所以我们只需要一个变量prev保存在中序遍历时,上一次被访问的节点。因为在中序遍历的过程中,节点的值是依次递增的,因此求差值的方式应该是root.val - prev.val,对该值取最小,就是BST任意两个节点的最小差值。
这里需要注意一个细节:中序遍历时的第一个节点,并没有prev节点。此时应该怎么办?其实就是不求第一个和上个节点的差值就行了。可以把prev初始化为None,遍历时对prev进行一个判断,如果prev为None,说明当前遍历的是中序遍历的第一个节点,跳过求差值;此后的遍历中,在每次求完diff之后,把prev设置为当前遍历的节点。

代码

# 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):
        self.vals = []
        self.inOrder(root)
        return min([self.vals[i + 1] - self.vals[i] for i in range(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) O(N)
空间复杂度: O ( N ) O(N) O(N)

文章来源:https://blog.csdn.net/weixin_43186779/article/details/135609217
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。