首页 > itarticle > [leetcode] problem 111 – minimum depth of binary tree

[leetcode] problem 111 – minimum depth of binary tree

admin 11月 13, 2020 0

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note

A leaf is a node with no children.

Example

Given binary tree [3,9,20,null,null,15,7],

return its minimum depth = 2.

O(n) runtime, O(log n) space – Depth-first traversal

public class  {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public int minDepth(TreeNode root) {
    if (root == null)
        return 0;
    
    if (root.left == null)
        return minDepth(root.right) + 1;

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

    return Math.min(minDepth(root.right), minDepth(root.left)) + 1;
}

O(n) runtime, O(n) space – Breadth-first traversal

public class  {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public int minDepth(TreeNode root) {
    if (root == null)
        return 0;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    TreeNode levelEnd = root;
    int depth = 1;

    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();

        if (current.left == null && current.right == null)
            break;

        if (current.left != null)
            queue.offer(current.left);

        if (current.right != null)
            queue.offer(current.right);

        if (current == levelEnd) {
            levelEnd = current.right == null ? current.left : current.right;
            depth++;
        }
    }

    return depth;
}