题意分析

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

    前置知识

  • 首先，我们需要知道什么是二叉树，简单来说就是一个一棵树由根节点，左叶子节点和右叶子节点组成，而左右叶子节点又可以单独看成一个二叉树。即每个节点最多有两个子节点。然后就是一层层的递归下去。
    看一张图（有点丑，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
}