LeetCode 111 最長公共字首

2022-09-22 06:41:45 字數 1726 閱讀 4323

問題描述:

給定一個二叉樹,找出其最小深度。

最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。

說明:葉子節點是指沒有子節點的節點。

示例:

給定二叉樹[3,9,20,null,null,15,7],

3

/ \9 20

/ \

15 7

返回它的最小深度  2。

思路:用層序遍歷,發現為葉子節點時,返回其所在的層即為最小深度。

方法1:

1

class

solution(object):

2def

mindepth(self, root):

3"""

4:type root: treenode

5:rtype: int

6"""7if

notroot:

8return09

ifnot root.left and

notroot.right:

10return 1

11 last =0

12 front = -1

13 rear = -1

14 level =0

15 l_list=

1617 rear += 1

18 level += 1

19while front 20 front += 1

21 p =l_list.pop(0)

22if

not p.left and

notp.right:

23return

level

24if

p.left:

2526 rear += 1

27if

p.right:

2829 rear += 1

30if front ==last:

31 level += 1

32 last = rear

方法2:(遞迴)當左子樹為null時,高度為右子樹+1,樹的最小高度為左子樹最小的高度+1.

1

class

solution(object):

2def

mindepth(self, root):

3"""

4:type root: treenode

5:rtype: int

6"""7if

root:

8if root.left==none:

9return self.mindepth(root.right)+1

10elif root.right==none:

11return self.mindepth(root.left)+1

12else:13

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

14else:15

return 0

2018-09-10 19:23:25