剑指offer刷题7——搜索与回溯算法(简单)

剑指 Offer 32 - I. 从上到下打印二叉树

难度 中等

从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。

例如: 给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回:

1
[3,9,20,15,7]

提示:

  1. 节点总数 <= 1000

思路

层序遍历。

特殊情况:树为空,直接返回一个空容器

算法流程:

  1. 将根节点入队,进入循环
  2. 队头元素出队的同时队头元素的左右非空节点入队,同时将队头元素的数值推入返回的容器内。 ### 代码 ```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: vector levelOrder(TreeNode root) { vector 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; } };