剑指offer之面试题23:从上往下打印二叉树
题目:从上往下打印出二叉树的每个节点,同层节点从左至右打印。(BFS)
思路:
根据题目,想到层序遍历时,按照从上到下,从左到右的访问每一个结点,用到一个辅助队列(先进先出才能保证从左到右的访问)。
代码:
/* 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> v1; //先进先出 queue<TreeNode *> q1; if(root==NULL) { return v1; } q1.push(root); v1.push_back(root->val); while(!q1.empty()) { TreeNode* tmp=q1.front(); q1.pop(); if(tmp->left!=NULL) { q1.push(tmp->left); v1.push_back(tmp->left->val); } if(tmp->right!=NULL) { q1.push(tmp->right); v1.push_back(tmp->right->val); } } return v1; } };