Simple PYTHON solution 95% - 1 queue


  • 0
    V

    Use a standard BFS approach to complete level order traversal. Then simply reverse the top down result to get the bottom up result.

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    from collections import deque
    
    class Solution(object):
        def levelOrderBottom(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            q = deque([root])
            nodesCurrLevel = 1
            nodesNxtLevel = 0
            ret = []
            currLevel = []
            while len(q):
                currNode = q.popleft()
                nodesCurrLevel -= 1
                if currNode:
                    currLevel.append(currNode.val)
                    q.append(currNode.left)
                    q.append(currNode.right)
                    nodesNxtLevel += 2
    
                if nodesCurrLevel == 0:
                    nodesCurrLevel = nodesNxtLevel
                    nodesNxtLevel = 0
                    if len(currLevel):
                        ret.append(currLevel)
                        currLevel = []
            
            return ret[::-1]
                    
            
            
    

Log in to reply
 

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