Leetcode skimming: binary tree 22 (minimum absolute difference of binary search tree)

530. The minimum absolute difference of binary search tree

Force button topic link

Give you a binary search tree with nonnegative nodes , Please calculate the minimum absolute value of the difference between any two nodes in the tree .

Example ：

Tips ： At least in the tree 2 Nodes .

Binary search tree , Itself in ascending order , The decreasing , Intermediate order traversal to obtain value , Compare one by one

public int getMinimumDifference(TreeNode root) {
    
        List<Integer> result = new ArrayList();
        // Traverse the binary tree to get the result set 
        // Binary search tree itself is ascending 
        inorderTraversal(root, result);
        // Define an impossible maximum 
        int minimumDifference = 100001;
        for (int i = 1; i < result.size(); i++) {
    
            if (minimumDifference == 0) {
    
                return minimumDifference;
            }
            if (result.get(i) - result.get(i - 1) < minimumDifference) {
    
                minimumDifference = result.get(i) - result.get(i - 1);
            }
        }
        return minimumDifference;
    }

    public void inorderTraversal(TreeNode root, List<Integer> result) {
    
        if (root == null) {
    
            return;
        }
        // In the sequence traversal   Left   in   Right 
        inorderTraversal(root.left, result);
        result.add(root.val);
        inorderTraversal(root.right, result);
    }

Looking at the solution, I found that my writing was complicated , The solution of the problem is written with the parent pointer , Comparison in traversal .

 TreeNode parent;
    int result = Integer.MAX_VALUE;

    public void inorderTraversalParent(TreeNode root) {
    
        if (root == null) {
    
            return;
        }
        // In the sequence traversal   Left   in   Right 
        inorderTraversalParent(root.left);
        if (parent != null) {
    
            if (result > root.val - parent.val) {
    
                result = root.val - parent.val
            }
        }
        parent = root;
        inorderTraversalParent(root.right);
    }

    public int getMinimumDifference2(TreeNode root) {
    
        inorderTraversalParent(root);
        return result;
    }