This is the 27th day of my participation in the August More Text Challenge

Today is the 27th day for me to participate in the August review. Today, I will bring you the algorithm problem about binary tree correlation is the minimum absolute difference of binary search tree. The text is as follows:

The title

You are given a binary search tree in which all nodes are non-negative. Compute the minimum absolute value of the difference between any two nodes in the tree.

Example:

Input: 1\3/2 Output: 1 Explanation: The minimum absolute difference is 1, where the absolute value of the difference between 2 and 1 is 1 (or 2 and 3).Copy the code

Their thinking

The binary tree is a binary search tree, so we can use the middle order traversal way to traverse the whole binary tree, the result will be an ordered array, and then loop through the array again, through the value of the number group, to get the minimum absolute difference;

The above solution is a feasible solution. In addition, we can also find the minimum absolute difference by traversing and searching. The specific ideas are as follows:

  1. Define a global variable ans to record the minimum absolute difference, and define a global variable to record the last value of the binary tree traversal;
  2. If a null node is encountered, return directly;
  3. If pre = -1, it means that the node is the root node, and the value of the root node is assigned to Pre; otherwise, the absolute value of the difference between the current node and the previous node is calculated and compared with ANS, and the minimum value is assigned to ANS.

Code implementation

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    int ans;
    int pre;
    public int getMinimumDifference(TreeNode root) {
        ans = Integer.MAX_VALUE;
        pre = -1;
        inOrder(root);
        return ans;
    }

    public void inOrder(TreeNode node){
        if (node == null) {
            return;
        }
        inOrder(node.left);
        if (pre == -1) {
            pre = node.val;
        } else{ ans = Math.min(ans, node.val - pre); pre = node.val; } inOrder(node.right); }}Copy the code

The last

Complexity analysis:

  • Time complexity: O(n), where N is the number of nodes in the binary search tree. Each node is accessed once and only once in the middle-order traversal, so the total time complexity is O(n).

  • Space complexity: O(n). The spatial complexity of recursive functions depends on the stack depth of the recursion, and the stack depth reaches O(n) level in the case of a binary search tree as a chain.