Binary tree - 530. Minimum absolute difference of binary search tree

1 Title Description

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 .

Inherent 783. Binary search tree node minimum distance It's actually the same question

2 Title Example

Example 1：
Input ：root = [4,2,6,1,3]
Output ：1

Example 2：
Input ：root = [1,0,48,null,null,12,49]
Output ：1

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/minimum-absolute-difference-in-bst

3 Topic tips

The number of nodes in the tree ranges from [2, 10^4]
0 <= Node.val <= 10^5

4 Ideas

Consider for ascending arrays aa Find the minimum of the absolute value of the difference between any two elements , The answer must be the minimum of the difference between two adjacent elements , namely

among n Is an array α The length of . Any other interval greater than or equal to 2 Subscript pair of (i,j) The difference between the elements of — Greater than subscript pair (i,i＋1) The difference between the elements of , So no
To be considered again .
Back to the subject , This problem requires the minimum absolute value of the difference between any two nodes of the binary search tree , We know that the binary search tree has a property that the sequence of values obtained by order traversal in the binary search tree is incrementally ordered , Therefore, as long as we get the value sequence after middle order traversal, we can use the method mentioned above to solve .
The simple way is through — Secondary middle order traversal saves the value in an array and then performs Traversal Solution , We can also use... In the middle order traversal process pre Variable holds the value of the precursor node , In this way, the answer can be updated while traversing , There is no need to explicitly create arrays to hold , It should be noted that pre The initial value of needs to be set to any negative number at the beginning of the tag , The following code is set to -1.
Complexity analysis
Time complexity :O(n), among n The number of nodes in the binary search tree . Each node will be visited once and only once in the middle order traversal , So the total time complexity is O(n).
Spatial complexity :O(n). The space complexity of recursive functions depends on the stack depth of recursion , The stack depth in the binary search tree is — In the case of a chain, it will reach O(n) Level .

5 My answer

class Solution {
    
    int pre;
    int ans;

    public int getMinimumDifference(TreeNode root) {
    
        ans = Integer.MAX_VALUE;
        pre = -1;
        dfs(root);
        return ans;
    }

    public void dfs(TreeNode root) {
    
        if (root == null) {
    
            return;
        }
        dfs(root.left);
        if (pre == -1) {
    
            pre = root.val;
        } else {
    
            ans = Math.min(ans, root.val - pre);
            pre = root.val;
        }
        dfs(root.right);
    }
}