leetcode/107-binary-tree-level-order-traversal-ii.py at master · anantkaushik/leetcode · GitHub

Name: leetcode/107-binary-tree-level-order-traversal-ii.py at master · anantkaushik/leetcode · GitHub
Rating: 4.7 (6031 reviews)
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
64
65
"""
Problem Link: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

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,null,null,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:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
classSolution_Iterative:
deflevelOrderBottom(self, root: TreeNode) ->List[List[int]]:
ifrootisNone:
return []

current, res= [root], []

whilecurrent:
nex, temp= [], []
fornincurrent:
temp.append(n.val)
ifn.left:
nex.append(n.left)
ifn.right:
nex.append(n.right)
current=nex
res.append(temp)
returnres[::-1]

classSolution_Recursive:
deflevelOrderBottom(self, root: TreeNode) ->List[List[int]]:
levels= []
ifnotroot:
returnlevels

defhelper(node,level):

iflen(levels)==level:
levels.append([])

levels[level].append(node.val)

ifnode.left: helper(node.left, level+1)
ifnode.right: helper(node.right, level+1)

helper(root,0)

returnlevels[::-1]