111. Minimum Depth of Binary Tree

思路1: 递归，分类讨论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # 6 star, 分类讨论的情形比较巧妙，一开始做错了
        # todo, 需要掌握
        if not root:
            return 0
        return self._minDepth(root)

    def _minDepth(self, node):
        if not node.left and not node.right:
            return 1
        elif node.left and node.right:
            return min(self._minDepth(node.left), self._minDepth(node.right)) + 1
        elif node.left:
            return self._minDepth(node.left) + 1
        else:
            return self._minDepth(node.right) + 1

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func minDepth(root *TreeNode) int {
	if root == nil {return 0}
	if root.Right == nil && root.Left == nil {return 1}
	queue := []*TreeNode{root}
	depth := 0
	for len(queue) > 0 {
		depth += 1
		nextLevel := []*TreeNode{}
		for _, node := range queue {
			if node.Left == nil && node.Right == nil {return depth}
			if node.Left != nil {nextLevel = append(nextLevel, node.Left)}
			if node.Right != nil {nextLevel = append(nextLevel, node.Right)}
		}
		queue = nextLevel
	}
	return depth


}

思路2: bfs, 在广度优先遍历的过程中，每遍历一层就高度加一，如果某一个节点是叶子节点，那么当前的高度就是最小高度。

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        depth, curr_level = 0, [root]
        while curr_level:
            depth += 1
            next_level = []
            for n in curr_level:
                left, right = n.left, n.right
                if left is None and right is None:
                    return depth
                if left:
                    next_level.append(left)
                if right:
                    next_level.append(right)
            curr_level = next_level
        return depth