[牛客网刷题 Day4] JZ32 从上往下打印二叉树

题目

不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面，返回。

思路

可以用队列的思路：

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

答案

答案里有递归的思路，还是搞不太明白是咋回事呢

import queue
class Solution:
    def traverse(self, root: TreeNode, res: List[List[int]], depth: int):
        if root:
            # 新的一层
            if len(res) < depth: 
                row = []
                res.append(row)
                row.append(root.val)
            # 读取该层的一维数组，将元素加入末尾
            else: 
                row = res[depth -1]
                row.append(root.val)
        else: 
            return 
        # 递归左右时深度记得加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)
        #加入一维数组
        for i in temp:
            for j in i:
                res.append(j)
        return res