(第24天)【leetcode题解】二叉树的层序遍历

102、二叉树的层序遍历

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

思路

1. 层序遍历

就是从根节点一层一层的从左到右遍历

2. 数据结构选择

选择队列这种先入先出的结构来辅助实现

3. 整体算法

从root开始，每遍历到一个节点，在把它放入结果集的同时，把它的子节点按从左到右的顺序加入队列。

代码

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> res;//结果集，是一个二维数组while (!que.empty()) {int size = que.size();//当前节点的层数有几个节点vector<int> vec;//一层的节点值for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node -> val);//把队头节点的值加入到结果集//同时把当前节点的左右节点按顺序加入队列if (node -> left) que.push(node -> left);if (node -> right) que.push(node -> right);}res.push_back(vec);}return res; }
};

递归法：

class Solution {
public:void order(TreeNode* cur, vector<vector<int>>& res, int depth) {if (cur == nullptr) return;//终止条件//加入结果集if (res.size() == depth) res.push_back(vector<int>());//先加入一层的容器res[depth].push_back(cur -> val);//在给这一层加入结果的值(每次递归都必然运行)//开始递归order(cur -> left, res, depth + 1);order(cur -> right, res, depth + 1);}vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;//结果集int depth = 0;//结果集中存储的节点层数order(root, res, depth);return res;}
};

107、二叉树的层序遍历II

题目描述

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

思路

正序把二叉树层序遍历的结果放入结果集，然后翻转结果集。

代码

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {queue<TreeNode*> que;vector<vector<int>> res;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();//当前这一层有几个节点vector<int> vec;for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node -> val);if (node -> left) que.push(node -> left);if (node -> right) que.push(node -> right);}res.push_back(vec);}reverse(res.begin(), res.end());//翻转return res;}
};

199、二叉树的右视图

题目描述

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

思路

层序遍历的时候，队列que每次存储一层数据，只要判断当前遍历到的数据是否是这一层最后一个数据即可。

代码

class Solution {
public:vector<int> rightSideView(TreeNode* root) {queue<TreeNode*> que;vector<int> res;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();//获得每一层的节点个数//进入循环，处理每层的节点数据for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (i == size - 1) res.push_back(node -> val);//遍历到每层的最后一个节点时，把这个节点加入结果集if (node -> left) que.push(node -> left);//把当前节点的左子节点加入队列if (node -> right) que.push(node -> right);//把当前节点的右子节点加入队列}} return res;}
};

637、二叉树的层平均值

题目描述

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

思路

层序遍历过程中，计算每层节点数据的总和，在计算平均值，把平均值加入结果集。

代码

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {queue<TreeNode*> que;vector<double> res;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();//每层节点的数目double sum = 0;//每层的总值for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();sum += node -> val;if (node -> left) que.push(node -> left);if (node -> right) que.push(node -> right);}res.push_back(sum / size);//把每层平均值加入结果集}return res;}
};

思考

1. 深度优先遍历的逻辑用栈来实现，先入后出，也就是递归的逻辑
2. 广度优先遍历的逻辑用队列实现，先入先出