从上往下打印二叉树
从上往下打印二叉树
http://www.nowcoder.com/questionTerminal/7fe2212963db4790b57431d9ed259701
描述
这是一篇指针初学者的题解。
知识点:二叉树,队列,树的层次遍历
难度:一星
题解
题目抽象:给出一颗二叉树,按照从上到下,从左到右的顺序遍历节点。也就是从上到下一层一层的遍历。
方法:层次遍历
这道题就是一个模板题,对队列的使用。因为要满足先进先出的特性。
- 初始化:一个队列queue<TreeNode*> q, 将root节点入队列q
- 如果队列不空,做如下操作:
- 弹出队列头,保存为node,将node的左右非空孩子加入队列
- 做2,3步骤,知道队列为空
如果不需要确定当前遍历到了哪一层,模板如下:
void bfs() { vis[] = 0; 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) } } } }
如果需要确定遍历到哪一层,模板如下;
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<int> PrintFromTopToBottom(TreeNode* root) { vector<int> ret; if (!root) return ret; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode *node = q.front(); q.pop(); ret.push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } return ret; } };
时间复杂度:O(n),二叉树的每个节点遍历一次
空间复杂度:O(n),二叉树的每个节点入队列一次