剑指offer-把二叉树打印成多行
题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
解题思路
还是用层序遍历的思想，设置一个队列初始推入根节点，每次删除队列顶的节点时，打印出来结点值，若其有左右子节点，则将左右子节点依次推入队列，如此遍历直到队列为空。
由于本题要求逐行输出，所以需要设置两个变量来保持分行：needPrint记录当前行仍需打印的节点数，nextLevel记录下一行需要打印的节点数。每打印完一个节点，将当前行剩下的结点数needPrint减1；每向队列放入一个子节点，将下一行的节点数nextLevel加1。打印完节点后若needPrint为0，则说明当前行节点已全部打印完，所以将needPrint设置为下一行的节点数nextLevel，同时将nextLevel置0.
代码
1 /* 2 struct TreeNode { 3 int val; 4 struct TreeNode *left; 5 struct TreeNode *right; 6 TreeNode(int x) : 7 val(x), left(NULL), right(NULL) { 8 } 9 }; 10 */ 11 class Solution { 12 public: 13 vector<vector<int> > Print(TreeNode* pRoot) { 14 vector<vector<int> > vs; 15 if(pRoot){ 16 vector<int> v; 17 queue<TreeNode*> q; 18 q.push(pRoot); 19 int needPrint=1; 20 int nextLevel=0; 21 while(q.size()){ 22 TreeNode* node=q.front(); 23 v.push_back(node->val); 24 needPrint--; 25 q.pop(); 26 if(node->left){ 27 q.push(node->left); 28 nextLevel++; 29 } 30 if(node->right){ 31 q.push(node->right); 32 nextLevel++; 33 } 34 if(needPrint==0){ 35 vs.push_back(v); 36 v.clear(); 37 needPrint=nextLevel; 38 nextLevel=0; 39 } 40 } 41 } 42 return vs; 43 } 44 45 };
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。