当前位置:网站首页>Minimum absolute difference of binary search tree (use medium order traversal as an ordered array)
Minimum absolute difference of binary search tree (use medium order traversal as an ordered array)
2022-07-07 08:04:00 【Hydrion-Qlz】
530. The minimum absolute difference of binary search tree
The difficulty is simple
Give you a binary search tree root node root
, return The minimum difference between the values of any two different nodes in the tree .
The difference is a positive number , Its value is equal to the absolute value of the difference between the two values .
Ideas
The problem needs to find the minimum of the absolute value of the difference between any two nodes on the binary search tree .
Notice the binary search tree , Binary search trees are ordered !
Traverse the binary search tree , What you get is actually an ordered array , Find the minimum difference on an ordered array , Is it very simple ?
package cn.edu.xjtu.carlWay.tree.minAbsoluteDifferenceInBST;
import cn.edu.xjtu.Util.TreeNode.TreeNode;
/** * 530. The minimum absolute difference of binary search tree * Give you a binary search tree root node root , return The minimum difference between the values of any two different nodes in the tree . * <p> * The difference is a positive number , Its value is equal to the absolute value of the difference between the two values . * <p> * https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/ */
public class Solution {
int result = Integer.MAX_VALUE;
TreeNode pre = null;
/** * If you think of it as a mid order traversal, it is an ordered array * * @param root * @return */
public int getMinimumDifference(TreeNode root) {
if (root == null) return 0;
traversal(root);
return result;
}
private void traversal(TreeNode root) {
if (root == null) {
return;
}
// Traverse left subtree
traversal(root.left);
// Data processing in the middle
if (pre != null) {
result = Math.min(result, root.val - pre.val);
}
pre = root;
// Traversal right subtree
traversal(root.right);
}
}
边栏推荐
- Linux server development, redis source code storage principle and data model
- C语言队列
- 2022制冷与空调设备运行操作复训题库及答案
- [2022 ciscn] replay of preliminary web topics
- [UVM foundation] what is transaction
- Operation suggestions for today's spot Silver
- Leanote private cloud note building
- 3D reconstruction - stereo correction
- 力扣(LeetCode)187. 重复的DNA序列(2022.07.06)
- 芯片资料 网站 易特创芯
猜你喜欢
Linux server development, MySQL transaction principle analysis
2022 welder (elementary) judgment questions and online simulation examination
[mathematical notes] radian
Leetcode 40: combined sum II
这5个摸鱼神器太火了!程序员:知道了快删!
Qt学习27 应用程序中的主窗口
LeetCode 40:组合总和 II
A bit of knowledge - about Apple Certified MFI
Common method signatures and meanings of Iterable, collection and list
padavan手动安装php
随机推荐
Linux server development, MySQL cache strategy
芯片资料 网站 易特创芯
Problem solving: unable to connect to redis
贝叶斯定律
Regular e-commerce problems part1
Li Kou interview question 04.01 Path between nodes
pytest+allure+jenkins安装问题:pytest: error: unrecognized arguments: --alluredir
Common method signatures and meanings of Iterable, collection and list
【数字IC验证快速入门】15、SystemVerilog学习之基本语法2(操作符、类型转换、循环、Task/Function...内含实践练习)
2022 Inner Mongolia latest advanced fire facility operator simulation examination question bank and answers
Wechat applet data binding multiple data
[matlab] when matrix multiplication in Simulink user-defined function does not work properly, matrix multiplication module in module library can be used instead
Niu Mei's mathematical problem --- combinatorial number
Operation suggestions for today's spot Silver
Linux server development, MySQL stored procedures, functions and triggers
3D reconstruction - stereo correction
Chip information website Yite Chuangxin
Linux server development, SQL statements, indexes, views, stored procedures, triggers
即刻报名|飞桨黑客马拉松第三期等你挑战
[UVM basics] summary of important knowledge points of "UVM practice" (continuous update...)