首页 > itarticle > 111 minimum depth of binary tree

111 minimum depth of binary tree

admin 1月 11, 2021 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.

思路

利用深度优先遍历（DFS），采用递归的方法解决这道问题。

在进行递归的时候，将每次递归的结果存储在数组中，根据题意，返回数组的最小值。

# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class (object):
    res = []
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if (root):
            self.res = []
            self.DFS(root, 1)
            return min(self.res)
        else:
            return 0
        
    def DFS(self, root, depth):
        if (root):
            if (root.left is None and root.right is None):
                self.res.append(depth)
            else:
                self.DFS(root.left, depth+1)
                self.DFS(root.right, depth+1)