Shulou(Shulou.com)06/01 Report--

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.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.