4 lines C# solution


  • 0
    W
    public class Solution {
    public int MinDepth(TreeNode root) {
        if(root==null) return 0;   
        if(root.left==null) return 1+MinDepth(root.right);
        if(root.right==null) return 1+MinDepth(root.left);
        return 1+Math.Min(MinDepth(root.left),MinDepth(root.right));
    }
    

    }


  • 0
    N

    Why that work?
    I can't understand..
    why :

    if(root.left==null) return 1+MinDepth(root.right);
    if(root.right==null) return 1+MinDepth(root.left);

  • 1
    K

    Very clean solution :)

    The only problem is that You have to traverse the whole tree.
    For example if left branch contains only one node and right branch contains 1 000 000 000 of them, your algorithm will have more than 1 000 000 000 operations instead of just 2.


  • 0
    T

    1+ is needed in all cases to account for the current node.
    Then the minimum of the left and right subtrees has to be calculated. The problem is if the node is missing 1 child: the recursive call will return 0 for that child. Then Math.min(0, x) == 0 // x > 0, which is incorrect, because we want to disregard the non-existent subtree that doesn't have a height.


  • 0
    T

    If you're wondering about the left-right swap, it's saving one line:
    if(root.left == null && root.right == null) return 1; by making a recursive call to root.right instead, which if it doesn't exist will return and then the 1+ will make sure the current node will be counted as a leaf. It's essentially an if spanning a recursive call.
    Note that even though it looks symmetrical, in the second if root.left will never be null.


Log in to reply
 

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