剑指offer刷题7——搜索与回溯算法(简单)
剑指 Offer 32 - I. 从上到下打印二叉树
难度 中等
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
1 | 3 |
返回:
1 | [3,9,20,15,7] |
提示:
节点总数 <= 1000
思路
层序遍历。
特殊情况:树为空,直接返回一个空容器
算法流程:
- 将根节点入队,进入循环
- 队头元素出队的同时队头元素的左右非空节点入队,同时将队头元素的数值推入返回的容器内。
代码
```C++
/**- 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:
vectorlevelOrder(TreeNode root) {
vectorres;
if(!root)
queuereturn res;
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;
}
};
评论