FilesExpand file tree

 master

/

kth_smallest.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

54 lines (46 loc) · 1.13 KB

 master

/

kth_smallest.py

Copy path

Top

File metadata and controls

• Code
• Blame

54 lines (46 loc) · 1.13 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

class Node:

def __init__(self, val, left=None, right=None):

self.val = val

self.left = left

self.right = right

def kth_smallest(root, k):

stack = []

while root or stack:

while root:

stack.append(root)

root = root.left

root = stack.pop()

k -= 1

if k == 0:

break

root = root.right

return root.val

class Solution(object):

def kthSmallest(self, root, k):

"""

:type root: TreeNode

:type k: int

:rtype: int

"""

count = []

self.helper(root, count)

return count[k-1]

def helper(self, node, count):

if not node:

return

self.helper(node.left, count)

count.append(node.val)

self.helper(node.right, count)

if __name__ == '__main__':

n1 = Node(100)

n2 = Node(50)

n3 = Node(150)

n4 = Node(25)

n5 = Node(75)

n6 = Node(125)

n7 = Node(175)

n1.left, n1.right = n2, n3

n2.left, n2.right = n4, n5

n3.left, n3.right = n6, n7

print(kth_smallest(n1, 2))

print(Solution().kthSmallest(n1, 2))