FilesExpand file tree

 master

/

binary-tree-level-order-traversal-ii.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

60 lines (52 loc) · 1.37 KB

 master

/

binary-tree-level-order-traversal-ii.py

Copy path

Top

File metadata and controls

• Code
• Blame

60 lines (52 loc) · 1.37 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

# Time: O(n)

# Space: O(n)

# Given a binary tree, return the bottom-up level order traversal of its nodes' values.

# (ie, from left to right, level by level from leaf to root).

#

# For example:

# Given binary tree {3,9,20,#,#,15,7},

# 3

# / \

# 9 20

# / \

# 15 7

# return its bottom-up level order traversal as:

# [

# [15,7],

# [9,20],

# [3]

# ]

# Definition for a binary tree node

class TreeNode(object):

def __init__(self, x):

self.val = x

self.left = None

self.right = None

class Solution(object):

def levelOrderBottom(self, root):

"""

:type root: TreeNode

:rtype: List[List[int]]

"""

if root is None:

return []

result, current = [], [root]

while current:

next_level, vals = [], []

for node in current:

vals.append(node.val)

if node.left:

next_level.append(node.left)

if node.right:

next_level.append(node.right)

current = next_level

result.append(vals)

return result[::-1]

if __name__ == "__main__":

root = TreeNode(3)

root.left = TreeNode(9)

root.right = TreeNode(20)

root.right.left = TreeNode(15)

root.right.right = TreeNode(7)

result = Solution().levelOrderBottom(root)

print result