# Python solutions (dfs recursively, dfs+stack, bfs+queue).

• ``````# dfs recursively
def levelOrderBottom1(self, root):
res = []
self.dfs(root, 0, res)
return res

def dfs(self, root, level, res):
if root:
if len(res) < level + 1:
res.insert(0, [])
res[-(level+1)].append(root.val)
self.dfs(root.left, level+1, res)
self.dfs(root.right, level+1, res)

# dfs + stack
def levelOrderBottom2(self, root):
stack = [(root, 0)]
res = []
while stack:
node, level = stack.pop()
if node:
if len(res) < level+1:
res.insert(0, [])
res[-(level+1)].append(node.val)
stack.append((node.right, level+1))
stack.append((node.left, level+1))
return res

# bfs + queue
def levelOrderBottom(self, root):
queue, res = collections.deque([(root, 0)]), []
while queue:
node, level = queue.popleft()
if node:
if len(res) < level+1:
res.insert(0, [])
res[-(level+1)].append(node.val)
queue.append((node.left, level+1))
queue.append((node.right, level+1))
return res``````

• what's the time complexity of each of these solutions?

• Regarding the Python recursion, we can either pass the result variable (must be a container type) as an argument of recursive method, or use `self.result` to read/write the result between recursion calls. I want to know which one is better?

• The complexity of `insert` is O(N), which makes the solution O(N^2).
So I changed it as follows:

``````def levelOrderBottom(self, root):
queue, res = collections.deque([(root, 0)]), []
while queue:
node, level = queue.popleft()
if node:
if level == len(res):
res.append([])
res[level].append(node.val)
queue.append((node.left, level + 1))
queue.append((node.right, level + 1))
return res[::-1]
``````

Here is my solution:

``````def levelOrderBottom(self, root):
res, queue = [], [root]
while queue:
res.append([node.val for node in queue if node])
queue = [child for node in queue if node for child in (node.left, node.right)]
return res[-2::-1]``````

• similar to you

``````class Solution(object):
def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
result = []
if not root:
return result
row = [root]
while any(row):
result = [[r.val for r in row]] + result
row = [i for rr in row for i in [rr.left, rr.right] if i]
return result
``````

• @caikehe shouldn't it be BFS +stack?

• @algowl

With the stack approach, right node enters stack first and left node follows. Then the pop() operation pops out left node and processes it (repeating the stack + pop steps for the left node's children nodes). Consequently, the right node will not be processed until the left node and its children have been processed completely. This is DFS.

• @lixzhang I see. Thanks.

• @caikehe Thank you. Recording level is a very good idea. I was struggling with that.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.