按之字形顺序打印二叉树
按之字形顺序打印二叉树
http://www.nowcoder.com/questionTerminal/91b69814117f4e8097390d107d2efbe0
描述
这是一篇针对初学者的题解。
知识点:二叉树,队列
难度:一星
题解
题目描述:给定一颗二叉树,假设根节点为第一层,按照奇数层,从左到右打印,偶数层,从右到左打印。
方法:队列
层次遍历打印二叉树,用队列实现。
有一句话,我觉得说的特别好:做题=解法+模板,意思就是说,对于一道题目,首先明白正确的解法已经解决该问题70%,剩下的就直接套模板。
所以BFS的模板为:
如果不需要确定当前遍历到了哪一层,模板如下:
void bfs() { vis[] = {0}; // or set queue<int> pq(start_val); while (!pq.empty()) { int cur = pq.front(); pq.pop(); for (遍历cur所有的相邻节点nex) { if (nex节点有效 && vis[nex]==0){ vis[nex] = 1; pq.push(nex) } } // end for } // end while }
上述是伪代码,不仅可用于二叉树,可针对所有用BFS解题。
如果需要确定遍历到哪一层,模板如下;
void bfs() { int level = 0; vis[] = {0}; // or set queue<int> pq(original_val); while (!pq.empty()) { int sz = pq.size(); while (sz--) { int cur = pq.front(); pq.pop(); for (遍历cur所有的相邻节点nex) { if (nex节点有效 && vis[nex] == 0) { vis[nex] = 1; pq.push(nex) } } // end for } // end inner while level++; } // end outer while }
此题跟“按层打印二叉树”,仅有一点区别,“按层打印二叉树”是每层都按照从左到右打印二叉树。
而此题是,按照奇数层,从左到右打印,偶数层,从右到左打印。
所以此题可直接套用模板,代码如下:
class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int>> ret; if (!pRoot) return ret; queue<TreeNode*> q; q.push(pRoot); int level = 0; while (!q.empty()) { int sz = q.size(); vector<int> ans; while (sz--) { 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); } ++level; if (!(level&1)) // 偶数层 反转一下 reverse(ans.begin(), ans.end()); ret.push_back(ans); } return ret; } };
时间复杂度:O(N^2)
空间复杂度:O(1), vecotr<vecotr<int>> 是必须要开的,不算在额外空间里