Python3、Java 实现「783. 二叉搜索树节点最小距离」

与你一起学算法

共 4844字,需浏览 10分钟

 ·

2021-04-14 20:37

783. 二叉搜索树节点最小距离

题目链接

https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/

也可以点击「阅读原文」直达题目链接。

题目描述

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

示例 1:


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

示例 2:


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

提示:

  • 树中节点数目在范围 [2, 100]

解题思路

这道题主要是考察二叉搜索树的性质,二叉搜索树的中序遍历得到的结果是升序排列的。要得到树中任意两个不同节点值之间的最小差值,那么只需要比较中序遍历得到的序列的相邻元素,求得最小值就可以了。

这道题看上去有点无从下手的感觉,但是碰到二叉搜索树,就一定要想到的中序遍历是有序的,这几乎是碰到二叉搜索树的必考点。

Python3 代码

# 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: TreeNode) -> int:
        self.inorder_result = []
        self.inorder(root)
        ans = 10 ** 5 + 1
        size = len(self.inorder_result)
        for i in range(1, size):
            ans = min(ans, self.inorder_result[i] - self.inorder_result[i - 1])
        return ans

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

Java 代码

/**
 * 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;
 *     }
 * }
 */

import java.util.List;
import java.util.ArrayList;
class Solution {
    private List<Integer> list;
    public int minDiffInBST(TreeNode root) {
        list = new ArrayList<>();
        this.inorder(root);
        int ans = 100001;
        for (int i = 1; i < list.size(); ++i) {
            ans = Math.min(ans, list.get(i) - list.get(i - 1));
        }
        return ans;
    }
    public void inorder(TreeNode root) {
        if (root != null) {
            this.inorder(root.left);
            this.list.add(root.val);
            this.inorder(root.right);
        }
    }
}

复杂度分析:

时间复杂度:

空间复杂度:

好了,今天的内容就到这里了。我最近在学习数据结构与算法的相关知识,也会在力扣进行每日一题的打卡。如果你最近在求职面试或者也在进行力扣进行每日一题的打卡的话,欢迎加入我们,后台回复「加群」即可。我一直坚信一个人走的更快,一群人走的更远。很多时候,只要坚持下去了,那么你就超越了很多人。

参考资料:

https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/solution/python3-java-shi-xian-783-er-cha-sou-suo-uika/

浏览 15
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报