LeetCode #111 Minimum Depth of Binary Tree

Posted on | Post modified | In , , , , , , , ,

Problem

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.

Example

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

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its minimum depth = 2.

Note

A leaf is a node with no children.

Solution1

Method: Recursive Breadth First Search

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0

        if not root.left or not root.right:
            return self.minDepth(root.left) + self.minDepth(root.right) + 1

        return min(self.minDepth(root.right),self.minDepth(root.left)) + 1

Solution2

Method: Iterative Breadth First Search

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        
        queue = collections.deque([(root, 1)])
        
        while queue:
            node, level = queue.popleft()
            if not node.left and not node.right:
                return level
            if node.left:
                queue.append([node.left, level + 1])
            if node.right:
                queue.append([node.right, level + 1])