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


  • 41
    C
    # 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

  • 0
    X

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


  • 0
    N

    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?


  • 7

    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]

  • 0
    L

    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
    

  • 0
    A

    @caikehe shouldn't it be BFS +stack?


  • 0
    L

    @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.


  • 0
    A

    @lixzhang I see. Thanks.


  • 0
    L

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


Log in to reply
 

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