目录
- LeetCode #102:Binary Tree Lever Order Traversal 二叉树的层序遍历
- 递归解法
- 迭代解法
- LeetCode #107:Binary Tree Level Order Traversal II - 二叉树的层序遍历 II
- 递归解法
- 迭代解法
- LeetCode #429:N-ary Tree Level Order Traversal - N 叉树的层序遍历
- LeetCode #637:Average of Levels in Binary Tree 二叉树的层平均值
- 广度优先搜索(BFS)
- 深度优先搜索(DFS)
本系列文章仅是 GitHub 大神 @halfrost 的刷题笔记 《LeetCode Cookbook》的提纲以及示例、题集的 C++转化。原书请自行下载学习。
本篇文章涉及新手应该优先刷的几道经典二叉树层序遍历算法题。
LeetCode #102:Binary Tree Lever Order Traversal 二叉树的层序遍历
给你一个二叉树,请你返回其按层序遍历得到的节点值。
递归解法
递归法并不符合层序遍历的初衷。递归是基于深度的,通过“解决到底”(即达到基准情况)将问题分解成规模更小的相同问题,直到问题小到可以直接解决(这被称为基准情况或递归终止条件),然后将这些小规模问题的解合并起来,即逐步回溯,形成原问题的解,而层序遍历需要一层一层地遍历,这显然不太符合广度优先搜索(BFS)的基本思想。
但是,我们依然可以利用递归实现二叉树的层序遍历。层序遍历是每一层的节点从左到右的遍历,在遍历的时候我们可以先遍历左子树,再遍历右子树。假设我们有如图的一颗二叉树:
遍历的顺序应为:3 -> 9 -> 3 -> 20 -> 15 -> 20 -> 7 。
因此,在遍历左子树或者右子树的时候,涉及到向上或者向下遍历,为了让递归的过程中的同
一层的节点放在同一个列表中,在递归时要记录深度 depth
;同时,每次遍历到一个新的 depth
,结果数组中没有对应 depth
的列表时,则在结果数组中创建一个新的列表保存该 depth
的节点。
//若当前行对应的列表不存在,则添加一个空列表
if (res.size() < depth) res.push_back(vector<int>());
我们利用递归的性质,每次向下深入均记录一次深度,并将相应节点值存储在对应深度的数组中,最终返回一个二维数组。
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if (root == nullptr) return res;level(root, 1, res);return res;}private:void level(TreeNode* root, int depth, vector<vector<int>>& res) {if (root == nullptr) return; // base case//若当前行对应的列表不存在,则添加一个空列表if (res.size() < depth) res.push_back(vector<int>());//将当前节点的值添加到当前深度的列表中res[depth - 1].push_back(root->val);//递归处理左子树if (root->left) level(root->left, depth + 1, res);//递归处理右子树if (root->right) level(root->right, depth + 1, res);}
};
该算法的时间复杂度为 O ( n ) \ O(n) O(n) ,由于维护了一个结果数组 res
,空间复杂度为 O ( n ) \ O(n) O(n) 。
需要注意的是,尽管这一解法使用了递归,但它在这里更多地是作为一种遍历树的手段,通过深度来控制每一层数据的收集。这种方法的优点是代码简洁,但不是处理大型二叉树时最高效的方法,过深的递归深度可能会导致栈溢出。对于大型树,迭代法更合适。
迭代解法
我们利用队列保存每一层的所有节点,把队列里的所有节点弹出队列,然后把这些节点各自的子节点入队列,以此来完成对每一层的遍历。
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if (root == nullptr) return res;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int levelSize = q.size(); //当前层的节点数vector<int> currentLevel;for (int i = 0; i < levelSize; ++i) {TreeNode* node = q.front();q.pop();//将当前节点的值加入当前层的结果中currentLevel.push_back(node->val); //若节点存在左子树,入队if (node->left) q.push(node->left);//若节点存在右子树,入队if (node->right) q.push(node->right);}//将当前层的结果加入最终结果中res.push_back(currentLevel); }return res;}
};
LeetCode #107:Binary Tree Level Order Traversal II - 二叉树的层序遍历 II
给你二叉树的根节点 root
,返回其节点值自底向上的层序遍历(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)。
与 #102 题(上一题)原理一致,按照正常层序遍历,获得结果后再将其逆序输出即可。
递归解法
我们依然是先遍历左子树,再遍历右子树,在递归时记录深度 depth
,不断更新每一层的 depth
,采用的 level()
方法与 #102 题一致。
class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> res;level(root, 1, res);reverse(res.begin(), res.end()); //反转结果return res;}private:void level(TreeNode* root, int depth, vector<vector<int>>& res) {if (root == nullptr) return;//若当前行对应的列表不存在,加一个空列表if (res.size() < depth) res.push_back(std::vector<int>());//将当前节点的值加入当前行的res中res[depth - 1].push_back(root->val);//递归处理左子树if (root->left) level(root->left, depth + 1, res);//递归处理右子树if (root->right) level(root->right, depth + 1, res);}
};
迭代解法
同 #102 题解法,最终只需要将结果逆序输出即可。
class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> res;if (root == nullptr) return res;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int levelSize = q.size();vector<int> currentLevel;for (int i = 0; i < levelSize; ++i) {TreeNode* node = q.front();q.pop();currentLevel.push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}res.push_back(currentLevel);}//反转结果,从底部到顶部reverse(res.begin(), res.end());return res;}};
LeetCode #429:N-ary Tree Level Order Traversal - N 叉树的层序遍历
给定一个 N 叉树,返回其节点值的层序遍历。 树的序列化输入是用层序遍历,每组子节点都由 null
值分隔。
与处理二叉树类似,我们依然利用队列保存每一层的所有节点,把队列里的所有节点弹出队列,然后把这些节点各自的子节点入队列。
class Solution {
public:vector<vector<int>> levelOrder(Node* root) {//如果根节点为空,则直接返回一个空的二维向量if (!root) return {};//存储层序遍历的结果vector<vector<int>> res;queue<Node*> q;//将根节点入队q.push(root);//当队列不为空时,进行循环遍历while (!q.empty()) {//获取当前层的节点数,即队列的大小int levelSize = q.size();//存储当前层的所有节点值vector<int> currentLevel;//遍历当前层的所有节点for (int i = 0; i < levelSize; ++i) {//从队列中取出当前节点Node* cur = q.front();q.pop();//将当前节点的值添加到 currentLevel 向量中currentLevel.push_back(cur->val);//遍历当前节点的所有子节点,并将它们入队for (Node* child : cur->children) q.push(child);}//将当前层的节点值向量添加到 res 中res.push_back(move(currentLevel)); //注意这里使用了 move(),以优化性能}//返回层序遍历的结果return res;}
};
该算法的时间复杂度为 O ( n ) \ O(n) O(n),空间复杂度为 O ( n ) \ O(n) O(n) 。
LeetCode #637:Average of Levels in Binary Tree 二叉树的层平均值
给定一个非空二叉树的根节点 root
,以数组的形式返回每一层节点的平均值。
广度优先搜索(BFS)
从根节点开始搜索,每一轮遍历同一层的全部节点,记录该层的节点总值和节点数,求该层平均值加入 res
结果集中,直至完全遍历整棵二叉树。
借鉴层序遍历的做法,我们可以使用队列存储待访问节点,只要确保在每一轮遍历时,队列中的节点是同一层的全部节点即可。
首先,初始化队列和结果集,将根节点入队列:
vector<double> res;
queue<TreeNode*> q;
q.push(root);
每一轮遍历时,将队列中的节点全部弹出,记录这些节点的数量以及它们的节点值之和,并计算这些节点的平均值,然后将这些节点的全部非空子节点加入队列,重复上述操作直到队列为空,遍历结束;同时,我们在每一轮遍历之前获得队列中的节点数量 levelSize
,遍历时只遍历 levelSize
个节点,即可满足每一轮遍历的是同一层的全部节点。
class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {vector<double> res;queue<TreeNode*> q;q.push(root);while (!q.empty()) {double sum = 0;int levelSize = q.size();for (int i = 0; i < levelSize; i++) {TreeNode* node = q.front();q.pop();//对每层节点求和sum += node->val;//加入非空子节点TreeNode* left = node->left, *right = node->right;//为避免定义变量类型失误,可以考虑如下写法:// auto left = node->left, right = node->right;if (left != nullptr) q.push(left);if (right != nullptr) q.push(right);}//计算每层节点值的平均值res.push_back(sum / levelSize);}return res;}
};
该算法的时间复杂度为 O ( n ) \ O(n) O(n) ,需要维护一个队列,空间复杂度为 O ( n ) \ O(n) O(n) 。
深度优先搜索(DFS)
我们维护两个数组,count
用于存储二叉树的每一层的节点数,sum
用于存储二叉树的每一层的节点值之和。搜索过程中记录递归深度 depth
,检查当前层数depth
是否已经存在于 sum
和 count
中,如果访问到的节点在第 i
层,则将 count[i]
的值自增,并将该节点的值添加到 sum[i]
;如果当前层数大于 sum.size()
,说明进入了新的层,就在 sum
和 count
的末端添加新的元素,分别初始化当前节点的值为 1 。
遍历结束之后,第 i
层的平均值即为 sum[i] / count[i]
。
class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {vector<int> count;vector<double> sum;//遍历树,并更新每一层的节点数量以及值的总和dfs(root, 0, count, sum);//存储每一层的平均值vector<double> res;//遍历 sum 和 count 向量,计算每一层的平均值并添加到 res 中int size = sum.size();for (int i = 0; i < size; i++) res.push_back(sum[i] / count[i]);return res;}private:void dfs(TreeNode* root, int depth, vector<int> &count, vector<double> &sum) {// base caseif (root == nullptr) return;//如果当前层数小于 sum 和 count 的大小,则更新该层的节点值总和以及节点数量if (depth < sum.size()) {sum[depth] += root->val;count[depth]++;} else {//如果当前层数大于 sum 和 count 的大小,说明遇到了新的层,需要添加新的元素sum.push_back(1.0 * root->val); //注意这里将值转换为 double 类型count.push_back(1);}//递归地对左子树进行深度优先搜索,层数加 1dfs(root->left, depth + 1, count, sum);//递归地对右子树进行深度优先搜索,层数也加 1dfs(root->right, depth + 1, count, sum);}
};