Обход порядка двоичного дерева в Python

Question

, поэтому дайте следующее дерево:

Я должен вернуть обход уровня дерева по порядку слева направо: таким образом, приведенный выше пример выведет список списков:

[[3], [9,20], [15,7]]

Я написал следующий код, идея заключается в сохранении значения узла и его глубинырекурсивно в очереди, затем итерируйте кортежи очереди и поместите их в промежуточный список O, если больше нет узла такой же глубины, добавьте O к выводу и очистите O и так далее. Однако мой код тайм-аут любой помощи?

 import queue

    class Solution:
        def levelOrder(self, root: TreeNode) -> List[List[int]]:
            def helper(root,res,level):
                if not root:
                    return res
                l=level+1
                res.put((root.val,level))
                helper(root.left,res,l)
                helper(root.right,res,l)

            res=queue.Queue()
            helper(root,res,0)

            d=1
            output=[]
            node,depth=res.get()
            output.append([node])
            while res:
                o=[]
                node,depth=res.get()
                while d ==depth:
                    o.append(node)
                    node,depth=res.get()
                else:
                    d+=1
                output.append(o)    

            return output

Answer 1

Вот мой код для итеративной реализации поиска в ширину (BFS) с узлами на каждом уровне в конечном выводе в одном списке:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def BFS(self, root) -> int:
        level=1
        current=(root, level)
        s=set()
        result=[]
        Q = [current]
        while Q:
            current=Q.pop()
            level=current[1]
            if current[0] not in s:
                result.append([current[0].val, level])
                s.add(current[0])
            if current[0].left:
                Q.insert(0,(current[0].left, level+1))
            if current[0].right:
                Q.insert(0,(current[0].right, level+1))
        output=[]
        temp=[]
        level=1
        for val in result:
            if val[1]==level:
                temp.append(val[0])
            elif val[1] > level:
                output.append(temp)
                temp=[val[0]]
                level+=1
        output.append(temp)
        return output

Тестирование:

n1=TreeNode(3)
n2=TreeNode(9)
n3=TreeNode(20)
n4=TreeNode(6)
n5=TreeNode(15)
n6=TreeNode(7)

n1.left=n2
n1.right=n3
n2.left=n4
n3.left=n5
n3.right=n6

sol1=Solution()
print(sol1.BFS(n1))
[[3], [9, 20], [6, 15, 7]]