FilesExpand file tree

 master

/

second-minimum-node-in-a-binary-tree.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

63 lines (57 loc) · 1.74 KB

 master

/

second-minimum-node-in-a-binary-tree.py

Copy path

Top

File metadata and controls

• Code
• Blame

63 lines (57 loc) · 1.74 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

# Time: O(n)

# Space: O(h)

# Given a non-empty special binary tree consisting of nodes with the non-negative value,

# where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes,

# then this node's value is the smaller value among its two sub-nodes.

#

# Given such a binary tree, you need to output the second minimum value in the set made of

# all the nodes' value in the whole tree.

#

# If no such second minimum value exists, output -1 instead.

#

# Example 1:

# Input:

# 2

# / \

# 2 5

# / \

# 5 7

#

# Output: 5

# Explanation: The smallest value is 2, the second smallest value is 5.

# Example 2:

# Input:

# 2

# / \

# 2 2

#

# Output: -1

# Explanation: The smallest value is 2, but there isn't any second smallest value.

# Definition for a binary tree node.

# class TreeNode(object):

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

import heapq

class Solution(object):

def findSecondMinimumValue(self, root):

"""

:type root: TreeNode

:rtype: int

"""

def findSecondMinimumValueHelper(root, max_heap, lookup):

if not root:

return

if root.val not in lookup:

heapq.heappush(max_heap, -root.val)

lookup.add(root.val)

if len(max_heap) > 2:

lookup.remove(-heapq.heappop(max_heap))

findSecondMinimumValueHelper(root.left, max_heap, lookup)

findSecondMinimumValueHelper(root.right, max_heap, lookup)

max_heap, lookup = [], set()

findSecondMinimumValueHelper(root, max_heap, lookup)

if len(max_heap) < 2:

return -1

return -max_heap[0]