前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python3、Java 实现「783. 二叉搜索树节点最小距离」

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

作者头像
与你一起学算法
发布2021-04-28 12:13:17
4320
发布2021-04-28 12:13:17
举报
文章被收录于专栏:与你一起学算法

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

题目链接

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

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

题目描述

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

示例 1:

代码语言:javascript
复制
输入:root = [4, 2, 6, 1, 3]
输出:1

示例 2:

代码语言:javascript
复制
输入:root = [1, 0, 48, null, null, 12, 49]
输出:1

提示:

  • 树中节点数目在范围 [2, 100]
0 <= Node.val <= 10^5

解题思路

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

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

Python3 代码

代码语言:javascript
复制
# 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 代码

代码语言:javascript
复制
/**
 * 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);
        }
    }
}

复杂度分析:

时间复杂度:

O(n)

空间复杂度:

O(n)

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

参考资料:

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-04-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 与你一起学算法 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 783. 二叉搜索树节点最小距离
    • 题目链接
      • 题目描述
        • 解题思路
          • Python3 代码
            • Java 代码
              • 复杂度分析:
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档