每日题解:LeetCode 783. 二叉搜索树节点最小距离

题目地址

题目描述

给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值

注意:本题与 530:https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/ 相同

img

示例 1:
输入:root = [4,2,6,1,3]
输出:1

img

示例 2:
输入:root = [1,0,48,null,null,12,49]
输出:1

解法

java

class Solution {
    int pre;
    int ans;

    public int minDiffInBST(TreeNode root) {
        ans=Integer.MAX_VALUE;
        pre = -1;
        dfs(root);
        return ans;
    }

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

python3

class Solution:
    def minDiffInBST(self, root: TreeNode) -> int:
        self.vals = []
        self.dfs(root)
        ans = float('inf')
        size = len(self.vals)
        for i in range(1, size):
            ans = min(ans, self.vals[i] - self.vals[i - 1])
        return ans

    def dfs(self, root: TreeNode) -> int:
        if root:
            self.dfs(root.left)
            self.vals.append(root.val)
            self.dfs(root.right)

解题思路

中序遍历

题目要求我们任意两节点的差的绝对值的最小值,由于二叉搜索树有个性质,二叉搜索树中序遍历得到的值序列是递增有序的,这样只要将二叉树的进行中序遍历,便可以存到数组,然后遍历找到绝对值的最小值

拿出中序遍历的模板

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

数组保存中序遍历结果

  1. 先中序遍历,把结果放在数组中;
  2. 然后遍历数组,对相邻元素求差,得到所有差值的最小值
class Solution:
    def minDiffInBST(self, root: TreeNode) -> int:
    	##保存中序数组
        self.vals = []
        self.dfs(root)
        ans = float('inf')
        size = len(self.vals)
        ##遍历数组
        for i in range(1, size):
            ans = min(ans, self.vals[i] - self.vals[i - 1])
        return ans

def dfs(self, root: TreeNode) -> int:
	##当root存在则遍历
    if root:
        self.dfs(root.left)
        self.vals.append(root.val)
        self.dfs(root.right)

保存上个节点

由于中序遍历是是一个有序递增的,保存整个值到数组,比较浪费空间,我们只要设置两个遍历全局遍历,一个指向上个节点的值,一个保存当前最小值

//上个节点的值
int pre;
//最小值
int ans;

if (root ==null){
 	return;
}
dfs(root.left);
//如果当前目录为根节点,上个值为根节点的值,然后继续遍历
if( pre == -1){
    pre=root.val;
}else{
    //获取最小值
    ans=Math.min(ans, root.val - pre);
    pre=root.val;  
}
dfs(root.right);
最近的文章

每日题解:LeetCode 208. 实现 Trie (前缀树)

题目地址题目描述Trie(发音类似"try")或者说前缀树是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。请你实现Trie类:Trie()初始化前缀树对象。voidinsert(Stringword)向前缀树中插…

继续阅读
更早的文章

每日题解:LeetCode 179. 最大数

题目地址题目描述给定一组非负整数nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。示例1:输入:nums=[10,2]输出:"210"示例2:输入:nums=[3,30,34,5,9]输出:&qu…

继续阅读