LeetCode 783. 二叉搜索树结点最小距离(Minimum Distance Between BST Nodes)
2024-08-26 12:26:43
783. 二叉搜索树结点最小距离
LeetCode783. Minimum Distance Between BST Nodes
题目描述
给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。
示例:
输入: root = [4,2,6,1,3,null,null]
输出: 1
解释:
注意: root 是树结点对象 (TreeNode object),而不是数组。
给定的树 [4,2,6,1,3,null,null] 可表示为下图:
4
/ \
2 6
/ \
1 3
最小的差值是 1, 它是节点 1 和节点 2 的差值, 也是节点 3 和节点 2 的差值。
注意:
- 二叉树的大小范围在 2 到 100。
- 二叉树总是有效的,每个节点的值都是整数,且不重复。
Java 实现
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
// 中等效率
private List<Integer> res = new ArrayList<>();
public int minDiffInBST(TreeNode root) {
if (root == null) {
return 0;
}
handle(root);
// Java 8 排序(由于题目是二叉排序树,中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。)
// res = res.stream().sorted(Integer::compareTo).collect(Collectors.toList());
int min = Integer.MAX_VALUE;
for (int i = 1; i < res.size(); i++) {
min = Math.min(res.get(i) - res.get(i - 1), min);
}
return min;
}
// 二叉树中序遍历
public void handle(TreeNode root) {
if (root == null) {
return;
}
handle(root.left);
res.add(root.val);
handle(root.right);
}
}
参考资料
- https://leetcode.com/problems/minimum-distance-between-bst-nodes/
- https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
最新文章
- Stack Overflow 排错翻译 - Closing AlertDialog.Builder in Android -Android环境中关闭AlertDialog.Builder
- HTML5学习总结-番外03 Angular Ionic
- CentOS安装Oracle数据库详细介绍及常见问题汇总
- [转]Flash Player、AIR、Flex SDK 大全
- 自定义readonly属性的用法
- hadoop中常见元素的解释
- 外部调用JS文件时出现中文乱码的解决办法
- CANopen笔记2
- pouchdb 安装使用
- ios存储 plist 偏好设置 自定义对象存储
- CSS(一) 引入方式 选择器 权重
- 【shell脚本练习】grep sed awk
- Yii2基本概念之——生命周期(LifeCycle)
- Android开发——子进程更新UI
- TechEmpower最新一轮的性能测试出炉,ASP.NET Core依旧表现不俗
- 学习笔记:spark Streaming的入门
- Git -- 本地 一个相同的新的分支 并 推送到远程仓库
- RxJava+Retrofit+OkHttp,一步一步封装网络框架;
- 干净的ssm框架项目
- MySQL压缩包zip安装
热门文章
- 范仁义html+css课程---2、html常用标签
- 范仁义web前端介绍课程---4、html、css、js初体验
- svn更新,清理,上传时出现乱码解决方案
- Nutch、Scrapy、Lucene、Heritrix、Solr、Sphinx
- tomcat中设置Java 客户端程序的http(https)访问代理
- 五、postman-sandbox
- Python3基础 函数 参数 在设定缺省值的情况下指明参数类型
- visual studio code跳转到定义处插件
- Spring cloud微服务安全实战-4-5搭建OAuth2认证服务器
- 软件定义网络基础---OF-Config协议