剑指offer-从上往下打印二叉树

本文为剑指 offer 系列第二十四篇。
主要知识点就是树的层序遍历，比较经典，也比较简单。

题目描述

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

解题思路

其实就是层序遍历，通过队列保存某一层的数据，然后依次的读取这一层数据，在遍历过程中，如果节点的左右子树不为空的话，继续加入到队列中，直到队列为空。

解题代码

/*
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) {
        if(!root) return {};
        vector<int> res;
        queue<TreeNode*> q{{root}};
        while(!q.empty()){
                auto a = q.front(); q.pop();
                res.push_back(a->val);
                if(a->left) q.push(a->left);
                if(a->right) q.push(a->right);
        }
        return res;
    }
};

时间复杂度为O(n),空间复杂度为O(n)

以上，本题结束！