Per-level BFS traversal in Python, easy understanding (46ms)


  • 0
    C
    class Solution(object):
        def levelOrder(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            if not root:
                return []
            ret = []
            # this stack keep tracks nodes in current level
            parent_stack = []
            # this stack tracks nodes in child level
            child_stack = []
            parent_stack.append(root)
            while len(parent_stack) != 0:
                cur_level = []
                for each in parent_stack:
                    cur_level.append(each.val)
                    if each.left:
                        child_stack.append(each.left)
                    if each.right:
                        child_stack.append(each.right)
                # for each level, replace parent level stack with child level stack
                parent_stack = child_stack
                # and clean child level stack
                child_stack = list()
                ret.append(cur_level)
            return ret
    
    

Log in to reply
 

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