[daiy4] jz32 print binary tree from top to bottom

subject

Print each node of the binary tree from top to bottom without branches , The nodes of the same layer are printed from left to right . For example, the input {8,6,10,#,#,2,1}, As shown in the following figure, the example binary tree , Print in turn 8,6,10,2,1( Empty nodes do not print , skip ), Please store the printed results in an array , return .

Ideas

You can use the idea of queue ：

from queue import Queue
class Solution:
    def PrintFromTopToBottom(self , root: TreeNode):
        # write code here
        res = []
        if root is None:
            print("")
        q = Queue()
        q.put(root)
        while not q.empty():
            for i in range(q.qsize()):
                node = q.get()
                res.append(node.val)
                if node.left:
                    q.put(node.left)
                if node.right:
                    q.put(node.right)
        return res

answer

There is a recursive idea in the answer , I still don't quite understand what's going on

import queue
class Solution:
    def traverse(self, root: TreeNode, res: List[List[int]], depth: int):
        if root:
            #  A new layer 
            if len(res) < depth: 
                row = []
                res.append(row)
                row.append(root.val)
            #  Read the one-dimensional array of this layer , Add the element to the end 
            else: 
                row = res[depth -1]
                row.append(root.val)
        else: 
            return 
        #  Remember to add the depth when recursing left and right 1
        self.traverse(root.left, res, depth + 1) 
        self.traverse(root.right, res, depth + 1)
        
    def PrintFromTopToBottom(self , root: TreeNode) -> List[int]:
        res = []
        temp = []
        if not root:
            return res
        self.traverse(root, temp, 1)
        # Add one-dimensional array 
        for i in temp:
            for j in i:
                res.append(j)
        return res