Totally different solution explained (Beats 96% Javascript submissions)


  • 1
    R
    1. Save the height values of all the branches of the tree in an array.
    2. Sort the array.
    3. Return the first value element of the array.
    var minDepth = function(root) {
        var res = [];
        
        var find = function(root, count){
            if(root.left === null & root.right === null)
                res.push(count);
            
            if(root.left !== null)
                find(root.left, count + 1);
            if(root.right !== null)
                find(root.right, count + 1);
        };
        
        if(root === null)
            return 0;
        
        find(root, 1);
        
        res.sort(function(a, b) {
            return a - b;
        });
        
        return res[0];
    };

  • 0
    N

    I took inspiration from your solution except made a slight performance improvement (don't need to sort at the end).

    Just keep a running minimum.

    var minDepth = function(root) {
        var minDepth = Infinity;
        
        if (root === null) {
            return 0;
        }
        
        function find(node, depth = 1) {
            if (node.left === null && node.right === null) {
                if (depth < minDepth) {
                    minDepth = depth;
                    if (minDepth === 1) {
                        return;
                    }
                }
            }
            
            if (node.left !== null) {
                find(node.left, depth+1);
            }
            
            if (node.right !== null) {
                find(node.right, depth+1);
            }
        }
        
        find(root);
        
        return minDepth;
    };
    
    

  • 0
    D

    Save height of all branches is O(n)
    Sorting is O(nlogn)

    Your solution in (n log n) which is not optimal solution that can be found.


Log in to reply
 

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