Using feature of BST, very clean Java solution


  • 0

    For each root, if we find the largest left child, and smallest right child , then minimum difference must be the lower one of |root - largest left child| and |root- smallest right child|.

    So for each node, find the minimum difference, and the lowest value among them is the answer.

    I use DFS to return the largest and smallest value of each subtree to the parent.

    public class Solution {
        int min = Integer.MAX_VALUE;
        public int getMinimumDifference(TreeNode root) {
            DFS(root);
            return min;
        }
        
        public int[] DFS(TreeNode root){
            if(root == null)    return new int[]{-1,-1};
            int[] left = DFS(root.left), right = DFS(root.right);
            if(left[1] != -1)    min = Math.min(min, Math.abs(root.val - left[1]));
            if(right[0] != -1)   min = Math.min(min, Math.abs(root.val - right[0]));
            
            return new int[]{left[0] == -1 ? root.val : left[0],right[1] == -1 ? root.val : right[1]};
        }
    }
    

  • 0

    Another naive solution. Collect all the nodes, sort them and find the minimum difference between contiguous numbers.

    public class Solution {
        public int getMinimumDifference(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            DFS(root,list);
            Collections.sort(list);
            int min = Integer.MAX_VALUE;
            for(int i = 1; i < list.size(); i++){
                min = Math.min(Math.abs(list.get(i) - list.get(i-1)), min);
            }
            return min;
        }
        
        public void DFS(TreeNode root, List<Integer> list){
            if(root == null)    return;
            list.add(root.val);
            DFS(root.left,list);
            DFS(root.right,list);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.