层序遍历练习

ops/2024/12/27 0:16:54/

层次遍历 II

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
在这里插入图片描述

思路

相对于102.二叉树的层序遍历,就是最后把result数组反转一下就可以了。

C++代码:

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;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);}result.push_back(vec);}reverse(result.begin(), result.end()); // 在这里反转一下数组即可return result;}
};

右视图

给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
在这里插入图片描述

思路

层序遍历的时候,判断是否遍历到单层的最后面的元素,如果是,就放进result数组中,随后返回result就可以了。

C++代码:

class Solution {
public:vector<int> rightSideView(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<int> result;while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (i == (size - 1)) result.push_back(node->val); // 将每一层的最后元素放入result数组中if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result;}
};

层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
在这里插入图片描述

思路

本题就是层序遍历的时候把一层求个总和再取一个均值。

C++代码:

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<double> result;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);}result.push_back(sum / size); // 将每一层均值放进结果集}return result;}
};

N叉树的层序遍历

给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。

例如,给定一个 3叉树 :
在这里插入图片描述

思路

这道题依旧是模板题,只不过一个节点有多个孩子了

C++代码:

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {queue<Node*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;for (int i = 0; i < size; i++) {Node* node = que.front();que.pop();vec.push_back(node->val);for (int i = 0; i < node->children.size(); i++) { // 将节点孩子加入队列if (node->children[i]) que.push(node->children[i]);}}result.push_back(vec);}return result;}
};

在每个树行中找最大值

您需要在二叉树的每一行中找到最大的值。

在这里插入图片描述

思路

层序遍历,取每一层的最大值

C++代码:

class Solution {
public:vector<int> largestValues(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<int> result;while (!que.empty()) {int size = que.size();int maxValue = INT_MIN; // 取每一层的最大值for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();maxValue = node->val > maxValue ? node->val : maxValue;if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(maxValue); // 把最大值放进数组}return result;}
};

每个节点的下一个右侧节点指针

给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

struct Node {int val;Node *left;Node *right;Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。
在这里插入图片描述

思路

本题依然是层序遍历,只不过在单层遍历的时候记录一下本层的头部节点,然后在遍历的时候让前一个节点指向本节点就可以了

C++代码:

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();// vector<int> vec;Node* nodePre;Node* node;for (int i = 0; i < size; i++) {if (i == 0) {nodePre = que.front(); // 取出一层的头结点que.pop();node = nodePre;} else {node = que.front();que.pop();nodePre->next = node; // 本层前一个节点next指向本节点nodePre = nodePre->next;}if (node->left) que.push(node->left);if (node->right) que.push(node->right);}nodePre->next = NULL; // 本层最后一个节点指向NULL}return root;}
};

每个节点的下一个右侧节点指针II

思路

这道题目说是二叉树,但116题目说是完整二叉树,其实没有任何差别,一样的代码一样的逻辑一样的味道

C++代码:

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();vector<int> vec;Node* nodePre;Node* node;for (int i = 0; i < size; i++) {if (i == 0) {nodePre = que.front(); // 取出一层的头结点que.pop();node = nodePre;} else {node = que.front();que.pop();nodePre->next = node; // 本层前一个节点next指向本节点nodePre = nodePre->next;}if (node->left) que.push(node->left);if (node->right) que.push(node->right);}nodePre->next = NULL; // 本层最后一个节点指向NULL}return root;}
};

二叉树的最大深度

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],
在这里插入图片描述

思路

使用迭代法的话,使用层序遍历是最为合适的,因为最大的深度就是二叉树的层数,和层序遍历的方式极其吻合。

class Solution {
public:int maxDepth(TreeNode* root) {if (root == NULL) return 0;int depth = 0;queue<TreeNode*> que;que.push(root);while(!que.empty()) {int size = que.size();depth++; // 记录深度for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return depth;}
};

最小深度

思路

需要注意的是,只有当左右孩子都为空的时候,才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

代码如下:(详细注释)

class Solution {
public:int minDepth(TreeNode* root) {if (root == NULL) return 0;int depth = 0;queue<TreeNode*> que;que.push(root);while(!que.empty()) {int size = que.size();depth++; // 记录最小深度for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (node->left) que.push(node->left);if (node->right) que.push(node->right);if (!node->left && !node->right) { // 当左右孩子都为空的时候,说明是最低点的一层了,退出return depth;}}}return depth;}
};

http://www.ppmy.cn/ops/145250.html

相关文章

C项目 天天酷跑(下篇)

上篇再博客里面有&#xff0c;接下来我们实现我们剩下要实现的功能 文章目录 碰撞检测 血条的实现 积分计数器 前言 我们现在要继续优化我们的程序才可以使这个程序更加的全面 碰撞的检测 定义全局变量 实现全局变量 void checkHit() {for (int i 0; i < OBSTACLE_C…

linux定时器操作

目录 1 简单示例2 timer_create方式2.1 SIGEV_SIGNAL信号方式通知2.2 SIGEV_THREAD启动线程方式通知2.3 参数 1 简单示例 #include <stdio.h> #include <stdlib.h> #include <sys/time.h> #include <signal.h> #include <unistd.h>void setup_t…

AI 视频:初识 Pika 2.0,基本使用攻略

网址&#xff1a;https://pika.art/ 目前 pika 2.0 免费使用&#xff0c;不过免费的期限是 12月23日 的 下午4点左右&#xff0c;在没有订阅的情况下&#xff0c;生成速度大致十几分钟左右&#xff0c;并且 Pikaffect 这个在 pika 2.0 使用不了&#xff0c;只能是 pika 1.5 使…

Linux零基础速成篇一(理论+实操)

前言&#xff1a;本教程适合Linux零基础学习&#xff0c;也适合Linux期末考试的小伙伴&#xff0c;从头到尾理论与实操相结合&#xff0c;让你快速对Linux进行了解和掌握。 一、Linux概述 为什么要学习Linux操作系统&#xff1f; 完全免费-开源 任何用户均可下载使用 安全…

leetcode hot100 翻转二叉树

226. 翻转二叉树 已解答 简单 相关标签 相关企业 给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val0, leftNone, rightNone): # …

docker commit生成的镜像瘦身

1、清除宿主系统的docker资源 docker system prune -a --volumes 2、清理容器内系统的临时文件和缓存 # 删除包管理器缓存 apt-get clean rm -rf /var/lib/apt/lists/* # 删除日志文件 rm -rf /var/log/* # 删除临时文件 rm -rf /tmp/* 3、安装docker squash工具&#xff0…

梳理你的思路(从OOP到架构设计)_设计模式Factory Method模式

目录 1、Factory Method模式 2、范例&#xff1a; Android FM(工厂)模式 3、Android里处处可见的FM模式的应用 1、Factory Method模式 誰來創建<T>的對象呢?例如&#xff0c; 剛才的Template Method模式內含一個EIT造形&#xff0c;那麼&#xff0c; 請問&#xff…

探索大语言模型的世界:入门指南

随着人工智能技术的飞速发展&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为诸多行业关注的焦点。从自然语言处理到生成式人工智能&#xff0c;LLMs 正在改变我们与技术互动的方式。如果你刚刚接触大语言模型&#xff0c;不知道从何下手&…