文章

LeetCode Minimum Depth of Binary Tree

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.

1
2
3
4
5
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Python 实现

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


# 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.
class Solution:
    def minDepth(self, root):
        if root == None:
            return 0
        minLeft = minRight = 1
        hasLeft = hasRight = False
        if root.left != None:
            minLeft = self.minDepth(root.left) + 1
            hasLeft = True
        if root.right != None:
            minRight = self.minDepth(root.right) + 1
            hasRight = True
        if not hasLeft:
            return minRight
        if not hasRight:
            return minLeft
        if minLeft <= minRight:
            return minLeft
        else:
            return minRight


tree = TreeNode(1)
tree.left = TreeNode(1)
treeFirstRight = TreeNode(1)
treeSecondLeft = TreeNode(1)
treeFirstRight.left = treeSecondLeft
# tree.right = treeFirstRight
print(Solution().minDepth(tree))

分析

显然递归是最容易想到的解决办法,每层的最小深度叠加出来就是最终的最小深度。

PS: 在学习Python,所以常用的Python解问题。

本文由作者按照 CC BY 4.0 进行授权