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

题目描述

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

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

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

示例 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)

数组保存中序遍历结果

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

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

清水1024