Description:
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],
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
Solution: 四種方案對比發(fā)現(xiàn)膝捞，value.insert(0,element)比value=[cache]+value要快！
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if root == None:
return []
value = []
node_ls = [root]
def helper(node_ls):
cache = []
for n in node_ls:
if n.left != None:
cache.append(n.left)
if n.right != None:
cache.append(n.right)
return cache
while node_ls:
value.append([n.val for n in node_ls])
node_ls = helper(node_ls)
return value[::-1]
Runtime: 44 ms, faster than 58.17% of Python3 online submissions for Binary Tree Level Order Traversal II.
Memory Usage: 13.3 MB, less than 77.88% of Python3 online submissions for Binary Tree Level Order Traversal II.
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if root == None:
return []
value = []
node_ls = [root]
def helper(node_ls):
cache = []
for n in node_ls:
if n.left != None:
cache.append(n.left)
if n.right != None:
cache.append(n.right)
return cache
while node_ls:
value.insert(0,[n.val for n in node_ls])
node_ls = helper(node_ls)
return value
Runtime: 32 ms, faster than 99.38% of Python3 online submissions for Binary Tree Level Order Traversal II.
Memory Usage: 13.4 MB, less than 72.12% of Python3 online submissions for Binary Tree Level Order Traversal II.
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if root == None:
return []
value = []
node_ls = [root]
last = root
cache = []
while node_ls:
curr = node_ls.pop(0)
cache.append(curr.val)
if curr.left != None:
node_ls.append(curr.left)
if curr.right != None:
node_ls.append(curr.right)
if curr == last:
value.insert(0,cache)
cache = []
if node_ls:
last = node_ls[-1]
return value
Runtime: 40 ms, faster than 82.81% of Python3 online submissions for Binary Tree Level Order Traversal II.
Memory Usage: 13.6 MB, less than 25.46% of Python3 online submissions for Binary Tree Level Order Traversal II.
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if root == None:
return []
value = []
node_ls = [root]
last = root
cache = []
while node_ls:
curr = node_ls.pop(0)
cache.append(curr.val)
if curr.left != None:
node_ls.append(curr.left)
if curr.right != None:
node_ls.append(curr.right)
if curr == last:
value = [cache] + value
cache = []
if node_ls:
last = node_ls[-1]
return value
Runtime: 44 ms, faster than 58.17% of Python3 online submissions for Binary Tree Level Order Traversal II.
Memory Usage: 13.7 MB, less than 22.73% of Python3 online submissions for Binary Tree Level Order Traversal II.
