剑指offer刷题7——搜索与回溯算法(简单)
剑指 Offer 32 - I. 从上到下打印二叉树
难度 中等
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
1 | 3 |
返回:
1 | [3,9,20,15,7] |
提示:
节点总数 <= 1000
思路
层序遍历。
特殊情况:树为空,直接返回一个空容器
算法流程:
- 将根节点入队,进入循环
- 队头元素出队的同时队头元素的左右非空节点入队,同时将队头元素的数值推入返回的容器内。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
vector<int> res;
if(!root)
return res;
queue<TreeNode*> Que;
Que.push(root);
while(!Que.empty())
{
res.push_back(Que.front()->val);
if(Que.front()->left != NULL)Que.push(Que.front()->left);
if(Que.front()->right != NULL)Que.push(Que.front()->right);
Que.pop();
}
return res;
}
};
评论