@TOC)

题目描述

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

题目分析

这道题遍历二叉树的方法，不是我们熟悉的前序中序和后序遍历，我们对于这种比较新颖的遍历顺序不太熟悉，这种时候我们可以先画画图来模拟我们的整个打印过程。

通过具体的分析过程，我们发现了从上到下打印整个二叉树的规律： 每次打印一个节点的的时候，我们将这个节点的左节点和右节点先后放入队列的末尾。接下来我们只需要按照队列的顺序依次打印出来就完成了。

所以说到底，我们需要借助一个队列来完成对于二叉树的遍历。

思路一：用队列来解决这个问题

/* 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) { queue<TreeNode*> queue;//定义队列 queue.push(root);//根节点的指针放入队列中 vector<int> record;//记录打印的值 while(!queue.empty()){ root = queue.front(); queue.pop(); if(!root) continue;//如果这个节点为空了，则跳过这次循环，去读取同层的别的节点 record.push_back(root -> val); queue.push(root -> left); queue.push(root -> right); } return record; } };

思路一：更漂亮美观的解决方式

/* 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) { queue<TreeNode*> queue; queue.push(root); vector<int> result; if(root==NULL) return result; while(!queue.empty()){ result.push_back(queue.front()->val);//存入当前节点的值 if(queue.front()->left!=NULL) queue.push(queue.front()->left); if(queue.front()->right!=NULL) queue.push(queue.front()->right); queue.pop();//对这个节点处理完后记得弹出 } return result; } };

小结

分析问题后抓住用队列来解决问题的关键。

参考文献

《剑指offer》

牛课网刷题链接link.