题解 | #求二叉树的层序遍历#
求二叉树的层序遍历
http://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3
题目的主要信息：
- 将给定二叉树按行从上到下、从左到右的顺序输出
- 输出到一个二维数组中，数组中每行就是二叉树的一层
举一反三：
学习完本题的思路你可以解决如下题目：
方法一：非递归（推荐使用）
知识点：队列
队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。
思路：
二叉树的层次遍历就是按照从上到下每行，然后每行中从左到右依次遍历，得到的二叉树的元素值。对于层次遍历，我们通常会使用队列来辅助：
因为队列是一种先进先出的数据结构，我们依照它的性质，如果从左到右访问完一行节点，并在访问的时候依次把它们的子节点加入队列，那么它们的子节点也是从左到右的次序，且排在本行节点的后面，因此队列中出现的顺序正好也是从左到右，正好符合层次遍历的特点。
具体做法：
- step 1：首先判断二叉树是否为空，空树没有遍历结果。
- step 2：建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面。
- step 3：每次进入一层，统计队列中元素的个数。因为每当访问完一层，下一层作为这一层的子节点，一定都加入队列，而再下一层还没有加入，因此此时队列中的元素个数就是这一层的元素个数。
- step 4：每次遍历这一层这么多的节点数，将其依次从队列中弹出，然后加入这一行的一维数组中，如果它们有子节点，依次加入队列排队等待访问。
- step 5：访问完这一层的元素后，将这个一维数组加入二维数组中，再访问下一层。
图示：
Java实现代码：
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
ArrayList<ArrayList<Integer> > res = new ArrayList();
if(root == null)
//如果是空，则直接返回空数组
return res;
//队列存储，进行层次遍历
Queue<TreeNode> q = new ArrayDeque<TreeNode>();
q.add(root);
while(!q.isEmpty()){
//记录二叉树的某一行
ArrayList<Integer> row = new ArrayList();
int n = q.size();
//因先进入的是根节点，故每层节点多少，队列大小就是多少
for(int i = 0; i < n; i++){
TreeNode cur = q.poll();
row.add(cur.val);
//若是左右孩子存在，则存入左右孩子作为下一个层次
if(cur.left != null)
q.add(cur.left);
if(cur.right != null)
q.add(cur.right);
}
//每一层加入输出
res.add(row);
}
return res;
}
}
C++实现代码：
class Solution {
public:
vector<vector<int> > levelOrder(TreeNode* root) {
vector<vector<int> > res;
if(root == NULL)
//如果是空，则直接返回空vector
return res;
//队列存储，进行层次遍历
queue<TreeNode*> q;
q.push(root);
TreeNode* cur;
while(!q.empty()){
//记录二叉树的某一行
vector<int> row;
int n = q.size();
//因先进入的是根节点，故每层节点多少，队列大小就是多少
for(int i = 0; i < n; i++){
cur = q.front();
q.pop();
row.push_back(cur->val);
//若是左右孩子存在，则存入左右孩子作为下一个层次
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);
}
//每一层加入输出
res.push_back(row);
}
return res;
}
};
Python实现代码
import queue
class Solution:
def levelOrder(self , root: TreeNode) -> List[List[int]]:
res = []
if not root:
# 如果是空，则直接返回空数组
return res
# 队列存储，进行层次遍历
q = queue.Queue()
q.put(root)
cur = None
while not q.empty():
# 记录二叉树的某一行
row = []
n = q.qsize()
# 因先进入的是根节点，故每层节点多少，队列大小就是多少
for i in range(n):
cur = q.get()
row.append(cur.val)
# 若是左右孩子存在，则存入左右孩子作为下一个层次
if cur.left:
q.put(cur.left)
if cur.right:
q.put(cur.right)
# 每一层加入输出
res.append(row)
return res
复杂度分析：
- 时间复杂度：，其中为二叉树的节点数，每个节点访问一次
- 空间复杂度：，队列的空间为二叉树的一层的节点数，最坏情况二叉树的一层为级
方法二：递归（扩展思路）
知识点：二叉树递归
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。
而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。
思路：
既然二叉树的前序、中序、后序遍历都可以轻松用递归实现，树型结构本来就是递归喜欢的形式，那我们的层次遍历是不是也可以尝试用递归来试试呢？
按行遍历的关键是每一行的深度对应了它输出在二维数组中的深度，即深度可以与二维数组的下标对应，那我们可以在递归的访问每个节点的时候记录深度：
void traverse(TreeNode root, int depth)
进入子节点则深度加1：
//递归左右时深度记得加1
traverse(root.left, depth + 1);
traverse(root.right, depth + 1);
每个节点值放入二维数组相应行。
res[depth - 1].push_back(root->val);
因此可以用递归实现：
- 终止条件： 遍历到了空节点，就不再继续，返回。
- 返回值： 将加入的输出数组中的结果往上返回。
- 本级任务： 处理按照上述思路处理非空节点，并进入该节点的子节点作为子问题。
具体做法：
- step 1：首先判断二叉树是否为空，空树没有遍历结果。
- step 2：使用递归进行层次遍历输出，每次递归记录当前二叉树的深度，每当遍历到一个节点，如果为空直接返回。
- step 3：如果遍历的节点不为空，输出二维数组中一维数组的个数（即代表了输出的行数）小于深度，说明这个节点应该是新的一层，我们在二维数组中增加一个一维数组，然后再加入二叉树元素。
- step 4：如果不是step 3的情况说明这个深度我们已经有了数组，直接根据深度作为下标取出数组，将元素加在最后就可以了。
- step 5：处理完这个节点，再依次递归进入左右节点，同时深度增加。因为我们进入递归的时候是先左后右，那么遍历的时候也是先左后右，正好是层次遍历的顺序。
Java实现代码：
import java.util.*;
public class Solution {
//记录输出
ArrayList<ArrayList<Integer> > res = new ArrayList();
void traverse(TreeNode root, int depth) {
if(root != null){
//新的一层
if(res.size() < depth){
ArrayList<Integer> row = new ArrayList();
res.add(row);
row.add(root.val);
//读取该层的一维数组，将元素加入末尾
}else{
ArrayList<Integer> row = res.get(depth - 1);
row.add(root.val);
}
}
else
return;
//递归左右时深度记得加1
traverse(root.left, depth + 1);
traverse(root.right, depth + 1);
}
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
if(root == null)
//如果是空，则直接返回
return res;
//递归层次遍历
traverse(root, 1);
return res;
}
}
C++实现代码：
class Solution {
public:
void traverse(TreeNode* root, vector<vector<int>>& res, int depth) {
if(root){
//新的一层
if(res.size() < depth)
res.push_back(vector<int>{});
//vector从0开始计数因此减1，在节点当前层的vector中插入节点
res[depth - 1].push_back(root->val);
}
else
return;
//递归左右时进入下一层
traverse(root->left, res, depth + 1);
traverse(root->right, res, depth + 1);
}
vector<vector<int> > levelOrder(TreeNode* root) {
vector<vector<int> > res;
if(root == NULL)
//如果是空，则直接返回空vector
return res;
traverse(root, res, 1);
return res;
}
};
Python实现代码
class Solution:
# 记录输出
res = []
def traverse(self, root: TreeNode, depth: int):
if root:
# 新的一层
if len(self.res) < depth:
row = []
self.res.append(row)
row.append(root.val)
# 读取该层的一维数组，将元素加入末尾
else:
row = self.res[depth -1]
row.append(root.val)
else:
return
# 递归左右时深度记得加1
self.traverse(root.left, depth+1)
self.traverse(root.right, depth+1)
def levelOrder(self , root: TreeNode) -> List[List[int]]:
if not root:
return self.res
self.traverse(root, 1)
return self.res
复杂度分析：
- 时间复杂度：，其中为二叉树的节点数，每个节点访问一次
- 空间复杂度：，最坏二叉树退化为链表，递归栈的最大深度为
查看6道真题和解析
