How to calculate the minimum absolute difference of binary search Tree by leetCode
This article will explain in detail how leetCode calculates the minimum absolute difference of the binary search tree. The editor thinks it is very practical, so I share it with you as a reference. I hope you can get something after reading this article.
1, the minimum absolute difference of binary search tree 1, a brief description of the problem
Give you a binary search tree in which all nodes are non-negative, and ask you to calculate the minimum absolute value of the difference between any two nodes in the tree.
2. Example description example:
Enter:
one
\
three
/
two
Output:
one
Explanation:
The minimum absolute difference is 1, where the absolute value of the difference between 2 and 1 is 1 (or 2 and 3).
3, the train of thought of solving the problem
Get the tree node data based on the middle order traversal, and solve the problem.
4, problem solving procedure
Import java.util.ArrayList
Import java.util.List
Public class GetMinimumDifferenceTest {
Public static void main (String [] args) {
TreeNode t1=new TreeNode (1)
TreeNode t2=new TreeNode (3)
TreeNode t3=new TreeNode (2)
T1.right=t2
T2.left=t3
Int minimumDifference = getMinimumDifference (T1)
System.out.println ("minimumDifference =" + minimumDifference)
}
Public static int getMinimumDifference (TreeNode root) {
List list = new ArrayList ()
If (root = = null) {
Return-1
}
Dfs (root, list)
System.out.println ("list =" + list)
Int [] toArray = list.stream () .mapToInt (x-> x) .toArray ()
Int pre = toArray [0]
Int res = Integer.MAX_VALUE
For (int I = 1; I < toArray.length; iTunes +) {
Res = Math.min (res, toArray [I]-pre)
Pre = toArray [I]
}
Return res
}
Private static void dfs (TreeNode root, List list) {
If (root = = null) {
Return
}
If (root.left! = null) {
Dfs (root.left, list)
}
List.add (root.val)
If (root.right! = null) {
Dfs (root.right, list)
}
}
}
This is the end of this article on "how leetCode calculates the minimum absolute difference of a binary search tree". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.
