JZ22 题解 | #从上往下打印二叉树#

题意分析

• 首先，这个题目没有说明数据是如何给出的，建议补一个样例的解释。另外，这个题目的难度应该属于简单范围。
  
  这是我对本题样例的理解。
• 题目给出一个二叉树的先序遍历的序列，需要我们求出这个二叉树的层序遍历的序列。样例解释如上面所示。

  前置知识

• 首先，我们需要知道什么是二叉树，简单来说就是一个一棵树由根节点，左叶子节点和右叶子节点组成，而左右叶子节点又可以单独看成一个二叉树。即每个节点最多有两个子节点。然后就是一层层的递归下去。
  看一张图（有点丑，hhh）
  
• 广度优先搜索(BFS)
  广度优先搜索指的是以某一个点为中心，不断向外进行辐射。广度是他的第一关键字。总是先访问能直接到达的节点，然后以被访问的节点的顺序依次访问他们所能到达的节点。另外还有个深度优先搜索，这个可以自行去学习。

思路分析

写法一

• 我们发现，题目是按照一个二叉树的先序遍历的结果给我们，如果我们需要进行一个层序遍历。那么我们需要先访问当前这一层的节点，然后访问完这些节点之后，我们需要就可以按照被访问的顺序去继续访问他们能访问的节点了。对于BFS，我们可以利用一个队列来存储我们需要访问的节点。当我们访问一个节点的时候，将这个节点的权值放入最终的答案里面，然后这节点出队。然后我们先判断左边的节点是否为空，如果为空，那么将这个节点指针入队，对右边的节点的判断也是一样。一直执行下去直到最后队列为空。另外记得特判根节点为空的情况。
• 代码，时间复杂度为O(N),空间复杂度也是O(N)

  /*
  struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
  };*/
  class Solution {
  public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> ans;
        // 特判为空的情况
        if(!root) return ans;  
        queue<treenode*> q;
        // 先将根节点放入队列里面
        q.push(root);  
        while(!q.empty()){
            TreeNode* now = q.front();
            // 出队
            q.pop();  
            ans.push_back(now->val);
            // 左边结点不为空，先将左节点入队
            if(now->left) q.push(now->left);  
            // 右边结点不为空，将右结点入队
            if(now->right) q.push(now->right); 
        }
        return ans;
    }
  };

  写法二

• 这个题目的思路比较有限，所以我暂时想不到第二种写法了。我就来补充一个Go语言的写法吧。Go语言的写法需要注意的是Go语言中没有天然写好的队列，需要我们自己实现。不过幸好Go语言为我们提供了切片，所以我们用切片来模拟队列就行了。
• 代码如下

  package main
  import . "nc_tools"
  func PrintFromTopToBottom( root *TreeNode ) []int {
    // write code here
    res := []int{}
    if(root==nil){
        return res
    }
    var q = []*TreeNode{root}
    // 用切片来模拟队列，到了切片尾部说明这个队列为空
    for i:=0;i<len(q);i++ {
        // 将当前结点入队
        now := q[i]
        res=append(res,now.Val)
        // 依次判断左右结点是否可以入队
        if(now.Left!=nil){
            q=append(q,now.Left)
        }
        if(now.Right!=nil){
            q=append(q,now.Right)
        }
    }
    return res
  }