|
| 1 | +## 102_(二叉树的层次遍历)Binary Tree Level Order Traversal |
| 2 | +## 1 问题描述、输入输出与样例 |
| 3 | +### 1.1 问题描述 |
| 4 | +给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。<br> |
| 5 | +### 1.2 输入与输出 |
| 6 | +输入：<br> |
| 7 | +* TreeNode* root：二叉树的根节点指针<br> |
| 8 | +输出：<br> |
| 9 | +* vector<vector<int>>：层次遍历的结果，是一个二维矢量的形式 |
| 10 | +### 1.3 样例 |
| 11 | +#### 1.3.1 样例1 |
| 12 | +输入: 给定二叉树: [3,9,20,null,null,15,7], |
| 13 | + |
| 14 | + 3 |
| 15 | + / \ |
| 16 | + 9 20 |
| 17 | + / \ |
| 18 | + 15 7 |
| 19 | + |
| 20 | +输出: |
| 21 | + |
| 22 | + [ |
| 23 | + [3], |
| 24 | + [9,20], |
| 25 | + [15,7] |
| 26 | + ] |
| 27 | + |
| 28 | +## 2 思路描述与代码 |
| 29 | +### 2.1 思路描述（基于队列的二叉树层次遍历） |
| 30 | +二叉树的层次遍历可以利用队列来做，其思路也很简单。<br> |
| 31 | +这里为了把每层的结果记录下来，对BFS的代码结构稍微改动了下，即里面用了个 for 循环做当前层遍历。<br> |
| 32 | +```cpp |
| 33 | +初始化二叉树层次遍历的二维矢量 res ; |
| 34 | +头结点入队; |
| 35 | +while( 队列不空 ){ |
| 36 | + 初始化当前层的遍历结果 level; |
| 37 | + 获取当前层的数目数 len; |
| 38 | + for( int i = 0; i < len; i++ ){ |
| 39 | + 取出当前层的节点tmp并保存至 level; |
| 40 | + 左右孩子非空则入队; |
| 41 | + } |
| 42 | + 将 level 保存至 res ; |
| 43 | +} |
| 44 | +返回 res ; |
| 45 | +``` |
| 46 | +比如给定二叉树: [3,9,20,null,null,15,7];<br> |
| 47 | +首先根节点3入队，然后进入 while 循环;<br> |
| 48 | +此时队列不空，有1个元素3，for 循环后有 res = {[3]}, 队列里面有元素[9, 20];<br> |
| 49 | +此时队列不空，有元素[9, 20]，for 循环后有 res = {[3],[9,20]}, 队列里面有元素[15, 7];<br> |
| 50 | +此时队列不空，有元素[15, 7]，for 循环后有 res = {[3],[9,20], [15,7]}, 队列里面没有元素;<br> |
| 51 | +此时队列空后，返回 res = {[3],[9,20], [15,7]} 。 |
| 52 | + |
| 53 | +### 2.2 代码 |
| 54 | +```cpp |
| 55 | +vector<vector<int>> levelOrder(TreeNode* root) { |
| 56 | + vector<vector<int>> res; |
| 57 | + //如果输入为空 |
| 58 | + if (root == NULL) { |
| 59 | + return res; |
| 60 | + } |
| 61 | + //队列做BFS |
| 62 | + queue<TreeNode*> q; |
| 63 | + q.push(root); |
| 64 | + while( !q.empty() ){ |
| 65 | + //获取当前层的数目 |
| 66 | + int len = q.size(); |
| 67 | + vector<int> level; |
| 68 | + TreeNode* tmp; |
| 69 | + for( int i = 0; i < len; i++ ){ |
| 70 | + //取一节点放入当前层的结果矢量里 |
| 71 | + tmp = q.front(); |
| 72 | + q.pop(); |
| 73 | + level.push_back(tmp->val); |
| 74 | + //当前层所有的节点如果有孩子节点则压入队列 |
| 75 | + if(tmp->left){ |
| 76 | + q.push(tmp->left); |
| 77 | + } |
| 78 | + if(tmp->right){ |
| 79 | + q.push(tmp->right); |
| 80 | + } |
| 81 | + } |
| 82 | + res.push_back(level); |
| 83 | + } |
| 84 | + return res; |
| 85 | +} |
| 86 | +``` |
| 87 | +## 3 思考与拓展 |
| 88 | +### 3.1 思考 |
| 89 | +本题，利用队列做二叉树的层次遍历并保存结果。当然你可以利用堆栈做，但是保存结果的方式不一样而已。 |
| 90 | +#### 3.1.1 其他方法 |
| 91 | +#### 3.1.1.1 基于堆栈的二叉树层次遍历 |
| 92 | +思路还是一致的，只是数据结构换了而已。在每层遍历的时候，需要改动的地方有: |
| 93 | +1. 入堆栈要右子树(如果有的话)先入，左子树(如果有的话)后入; |
| 94 | +2. 当前层遍历结果 level 要反序再 push_back 至 res。 |
| 95 | +#### 3.1.2 复杂度分析 |
| 96 | +方法|空间复杂度|时间复杂度 |
| 97 | +--- | --- | --- |
| 98 | +基于队列的二叉树层次遍历|O(2^h),h是树的高度|O(n) |
| 99 | +基于堆栈的二叉树层次遍历|O(2^h),h是树的高度|O(n)，由于多了一步反序，所以会比基于队列的慢一点 |
| 100 | +#### 3.1.3 难点分析 |
| 101 | +1. 采用什么数据结果做层次遍历 |
| 102 | +2. 如何保存每层的遍历结果 |
| 103 | +### 3.2 拓展 |
| 104 | +如果让你[锯齿形层次遍历](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/)呢？ |
0 commit comments