Minimum Depth of Binary Tree

# 問題

二分木が与えられたとき，最小の深さを求めよ．

# 答え

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class BinaryTreeNode:
    def __init__(self, key):
        self.key = key
        self.right = None
        self.left = None

def minimum_depth(root):
    # base case
    if root is None:
        return 0

    if root.left is not None and root.right is not None:
        return min(minimum_depth(root.left),  minimum_depth(root.right)) + 1
    elif root.left is None and root.right is not None:
        return minimum_depth(root.right) + 1
    elif root.left is not None and root.right is None:
        return minimum_depth(root.left) + 1
    else: # root.left is None and root.right is  None
        return 1