2020-05-12 剑指offer：从上往下打印出二叉树的每个

Query：从上往下打印出二叉树的每个节点，同层节点从左至右打印。

这个题目，其实就是对二叉树的遍历，每个节点应当遍历一次且仅遍历一次。通常，树的遍历有DFS和BFS。
首先给出DFS和BFS的代码模板。

def DFS(tree):
    if tree.root is None:
        return []
    visited = []
    stack = [tree.root]

    while stack:
        node = stack.pop()
        visited.append(node)

        # 处理当前层逻辑
        process(node)

        # 寻找node的子节点
        nodes = generate_children(node)
        # 将当前节点入栈 ； 一条路到黑
        if len(nodes)>0:
            stack.push(nodes[::-1])

def BFS(graph, strat):
    visited = set()
    queue = []
    queue.append(strat)

    while queue:
        node = queue.pop(0)
        visited.add(node)

        # 处理当前层
        process(node)

        # 寻找子节点
        nodes = generate_children(nodes)

        # 将所有当前层子节点入队列
        if len(nodes)>0:
            queue.push(nodes)

问题解决：
BFS：通过队列的结构辅助遍历

class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        res = []
        if not root:
            return []
        tmp = [root]
        while len(tmp)>0:
            a = tmp.pop(0)
            res.append(a.val)
            if a.left:
                tmp.append(a.left)
            if a.right:
                tmp.append(a.right)
        return res

DFS：使用递归思想，用level来控制从上到下、从左到右的顺序

class Solution:
  # 返回从上到下每个节点值列表，例：[1,2,3]
  def PrintFromTopToBottom(self, root):
      # write code here
      res = []
      visited = set()
      dic = {}
      def dfs(level,node):
          # 终止条件
          if not node:
              return
          visited.add(node)
          # 当前层逻辑
          if level in dic.keys():
              dic[level].append(node.val)
          else:
              dic[level]=[node.val]
          # 判断并进行下探
          if node.left and (node.left not in visited):
              dfs(level+1, node.left)
          if node.right and (node.right not in visited):
              dfs(level+1, node.right)
      dfs(0, root)
      for v in dic.values():
          res.extend(v)
      return res