当前位置:网站首页>Leetcode skimming: binary tree 22 (minimum absolute difference of binary search tree)
Leetcode skimming: binary tree 22 (minimum absolute difference of binary search tree)
2022-07-07 12:48:00 【Taotao can't learn English】
530. The minimum absolute difference of binary search tree
Give you a binary search tree with nonnegative nodes , Please calculate the minimum absolute value of the difference between any two nodes in the tree .
Example :
Tips : At least in the tree 2 Nodes .
Binary search tree , Itself in ascending order , The decreasing , Intermediate order traversal to obtain value , Compare one by one
public int getMinimumDifference(TreeNode root) {
List<Integer> result = new ArrayList();
// Traverse the binary tree to get the result set
// Binary search tree itself is ascending
inorderTraversal(root, result);
// Define an impossible maximum
int minimumDifference = 100001;
for (int i = 1; i < result.size(); i++) {
if (minimumDifference == 0) {
return minimumDifference;
}
if (result.get(i) - result.get(i - 1) < minimumDifference) {
minimumDifference = result.get(i) - result.get(i - 1);
}
}
return minimumDifference;
}
public void inorderTraversal(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
// In the sequence traversal Left in Right
inorderTraversal(root.left, result);
result.add(root.val);
inorderTraversal(root.right, result);
}
Looking at the solution, I found that my writing was complicated , The solution of the problem is written with the parent pointer , Comparison in traversal .
TreeNode parent;
int result = Integer.MAX_VALUE;
public void inorderTraversalParent(TreeNode root) {
if (root == null) {
return;
}
// In the sequence traversal Left in Right
inorderTraversalParent(root.left);
if (parent != null) {
if (result > root.val - parent.val) {
result = root.val - parent.val
}
}
parent = root;
inorderTraversalParent(root.right);
}
public int getMinimumDifference2(TreeNode root) {
inorderTraversalParent(root);
return result;
}
边栏推荐
- Master formula. (used to calculate the time complexity of recursion.)
- How to apply @transactional transaction annotation to perfection?
- [learn wechat from 0] [00] Course Overview
- Several ways to clear floating
- 密码学系列之:在线证书状态协议OCSP详解
- Charles: four ways to modify the input parameters or return results of the interface
- [difficult and miscellaneous]pip running suddenly appears modulenotfounderror: no module named 'pip‘
- 【从 0 开始学微服务】【01】什么是微服务
- Day-18 hash table, generic
- [learn micro services from 0] [02] move from single application to service
猜你喜欢
[pytorch practice] write poetry with RNN
[爬虫]使用selenium时,躲避脚本检测
Multi row and multi column flex layout
leetcode刷题:二叉树19(合并二叉树)
How to apply @transactional transaction annotation to perfection?
Common knowledge of one-dimensional array and two-dimensional array
OSPF exercise Report
IPv6 experiment
什么是ESP/MSR 分区,如何建立ESP/MSR 分区
In the small skin panel, use CMD to enter the MySQL command, including the MySQL error unknown variable 'secure_ file_ Priv 'solution (super detailed)
随机推荐
Common knowledge of one-dimensional array and two-dimensional array
OSPF exercise Report
Day-18 hash table, generic
HZOJ #240. 图形打印四
2022-07-07日报:GAN发明者Ian Goodfellow正式加入DeepMind
Pule frog small 5D movie equipment | 5D movie dynamic movie experience hall | VR scenic area cinema equipment
在字符串中查找id值MySQL
xshell评估期已过怎么办
解密GD32 MCU产品家族,开发板该怎么选?
Multi row and multi column flex layout
sql-lab (54-65)
ICLR 2022 | 基于对抗自注意力机制的预训练语言模型
About sqli lab less-15 using or instead of and parsing
Connect to blog method, overload, recursion
Talk about four cluster schemes of redis cache, and their advantages and disadvantages
聊聊Redis缓存4种集群方案、及优缺点对比
Four functions of opencv
test
RHSA first day operation
Image pixel read / write operation