3 lines in Every Language


  • 51

    We need to add the smaller one of the child depths - except if that's zero, then add the larger one. The first Python solution is the clearest because it lets me directly say exactly that.

    Python versions:

    def minDepth(self, root):
        if not root: return 0
        d = map(self.minDepth, (root.left, root.right))
        return 1 + (min(d) or max(d))
    
    def minDepth(self, root):
        if not root: return 0
        d, D = sorted(map(self.minDepth, (root.left, root.right)))
        return 1 + (d or D)
    

    C++ versions:

    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int L = minDepth(root->left), R = minDepth(root->right);
        return 1 + (min(L, R) ? min(L, R) : max(L, R));
    }
    
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int L = minDepth(root->left), R = minDepth(root->right);
        return 1 + (L && R ? min(L, R) : max(L, R));
    }
    
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int L = minDepth(root->left), R = minDepth(root->right);
        return 1 + (!L-!R ? max(L, R) : min(L, R));
    }
    
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int L = minDepth(root->left), R = minDepth(root->right);
        return L<R && L || !R ? 1+L : 1+R;
    }
    

    Java versions:

    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int L = minDepth(root.left), R = minDepth(root.right);
        return 1 + (Math.min(L, R) > 0 ? Math.min(L, R) : Math.max(L, R));
    }
    
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int L = minDepth(root.left), R = minDepth(root.right), m = Math.min(L, R);
        return 1 + (m > 0 ? m : Math.max(L, R));
    }
    
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int L = minDepth(root.left), R = minDepth(root.right);
        return L<R && L>0 || R<1 ? 1+L : 1+R;
    }
    

    Ruby version:

    def min_depth(root)
        return 0 if !root
        d, e = [min_depth(root.left), min_depth(root.right)].sort
        1 + (d>0 ? d : e)
    end
    

    Javascript version:

    var minDepth = function(root) {
        if (!root) return 0
        var L = minDepth(root.left), R = minDepth(root.right)
        return 1 + (Math.min(L, R) || Math.max(L, R))
    };
    

    C version:

    int minDepth(struct TreeNode* root) {
        if (!root) return 0;
        int L = minDepth(root->left), R = minDepth(root->right);
        return L<R && L || !R ? 1+L : 1+R;
    }
    

    C# version:

    public int MinDepth(TreeNode root) {
        if (root == null) return 0;
        int L = MinDepth(root.left), R = MinDepth(root.right);
        return L<R && L>0 || R<1 ? 1+L : 1+R;
    }

  • 1
    Q

    seems more concise with list comprehesion

    # remove redundant testing by introducing a helper func
    def minDepth(self, root):
        return 0 if not root else self.dfs(root)
    def dfs(self, root):
        return 1 + min([self.dfs(x) for x in (root.left,root.right) if x] or [0])
    
    # original version
    def minDepth1(self, root):
        if not root: return 0
        return 1 + min([self.minDepth(x) for x in (root.left,root.right) if x] or [0])  
    

  • 5
    O

    DFS 2-liner:

            h = map(self.minDepth, [root.left, root.right]) if root else [-1]
            return 1 + (min(h) or max(h))
    

    BFS 4-liner:

            l, i = [root], 1
            while l and root and all(n.left or n.right for n in l):
                l, i = [kid for n in l for kid in [n.left, n.right] if kid], i+1
            return i if root else 0
    

  • 0
    A

    same idea but your code is a much better one! So pythonic~


  • 0

    Thanks for sharing


  • 0
    B

    I think the essence of the python answer lies in the use of "or", it seems that if the operands around "or" are all numbers, it will return the first one unless the first one is zero, which serves exactly what we needed it to do.


  • 0
    S

    Nice for recursion version, but BFS might be more simple and easy to understand. Hope it helps:

    def minDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if not root:
                return 0
            
            depth = 0
            current_level = [root]
            
            while current_level:
                depth += 1
                next_level = []
                for node in current_level:
                    left = node.left
                    right = node.right
                    if not left and not right:
                        return depth
                    if left:
                        next_level.append(left)
                    if right:
                        next_level.append(right)
                current_level = next_level
            return depth
    

Log in to reply
 

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