一、题目描述

JZ22 从上往下打印二叉树
题目大意：从上往下打印出二叉树的每个节点, 同层节点从左至右打印

二、算法（二叉树的层序遍历）

解题思路

1. 本题是一道经典的二叉树层序遍历题, 考察了BFS搜索算法
2. 算法步骤：首先创建一个存放二叉树节点指针的队列, 并将根节点入队(若根为空, 直接返回空序列), 由于每层从左至右打印, 故对于每次取出的指针, 我们首先考虑它的左儿子是否存在, 再考虑它的右儿子是否存在, 这样可以保证出队序列满足题意

代码实现 (C++11)

/*
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;
        queue<TreeNode*> q;
        if(root) q.push(root);    // 若根存在, 则入队

        while(q.size()){
            TreeNode* node = q.front(); q.pop();    // 取出对头
            ans.push_back(node->val);    // 加入结果序列
            if(node->left) q.push(node->left);    // 考虑左儿子
            if(node->right) q.push(node->right);  // 考虑右儿子
        }

        return ans;
    }
};

时间复杂度：O(n), n为二叉树节点的个数
空间复杂度：O(n), 队列使用的空间

三、算法2（二叉树的前序遍历）

解题思路

1. 既然可以用BFS实现，同为搜索算法的DFS能否实现呢，答案是可以的
2. 使用DFS，我们需要知道遍历到的每个节点所在的层数，先序遍历可以保证每层节点加入的顺序是从左到右的，用一个二维数组data存放每层的节点即可，例如data[i]存放第i层的节点（从0开始），最后依次加入结果数组即可

代码实现（C++11）

class Solution {
public:
    vector<vector<int>> data;    // 存放每层的节点

    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> ans;
        dfs(root, 0);    // 深度优先搜素

        // 将data数组里面的元素依次放到ans数组中
        for(int i = 0; i < data.size(); i++){
            for(int j = 0; j < data[i].size(); j++){
                ans.emplace_back(data[i][j]);
            }
        }
        return ans;
    }

    void dfs(TreeNode* root, int height){
        if(!root) return;    // 为空即返回
        if(height >= data.size()) data.push_back(vector<int>());    // 到一个新高度, 存放一个空数组
        data[height].push_back(root->val);
        dfs(root->left, height + 1);     // 向左递归
        dfs(root->right, height + 1);    // 向右递归
    }
};

时间复杂度：O(n), n为二叉树节点数
空间复杂度：O(n), 递归和临时数组data使用的空间