层序遍历练习

层次遍历 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;
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/941529.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

京东大数据治理探索与实践 | 京东零售技术实践

京东大数据治理探索与实践 | 京东零售技术实践

01背景和方案 在当今的数据驱动时代&#xff0c;数据作为关键生产要素之一&#xff0c;其在商业活动中的战略价值愈加凸显&#xff0c;京东也不例外。 作为国内领先的电商平台&#xff0c;京东在数据基础设施上的投入极为巨大&#xff0c;涵盖数万台服务器、数 EB 级存储、数百…
阅读更多...
【论文阅读笔记】Learning to sample

【论文阅读笔记】Learning to sample

Learning to sample 前沿引言方法问题声明S-NET匹配ProgressiveNet: sampling as ordering 实验分类检索重建 结论附录 前沿 这是一篇比较经典的基于深度学习的点云下采样方法 核心创新点&#xff1a; 首次提出了一种学习驱动的、任务特定的点云采样方法引入了两种采样网络&…
阅读更多...
[AIGC知识] layout理解

[AIGC知识] layout理解

前言 要开组会了&#xff0c;随便讲个凑数吧。 参考论文 https://arxiv.org/html/2303.17189? 什么是layout数据&#xff1f; 像下图这样&#xff0c;Layout是每个图片的布局&#xff0c;其中包含一些物体的相应边界框和类别 layout信息如何整合表示并作为条件加入到网络…
阅读更多...
【macos java反编译工具Java Decompiler】

【macos java反编译工具Java Decompiler】

mac上能用的反编译工具 https://java-decompiler.github.io/
阅读更多...
C#+OpenCv深度学习开发(常用模型汇总)

C#+OpenCv深度学习开发(常用模型汇总)

在使用 OpenCvSharp 结合深度学习进行机器视觉开发时&#xff0c;有许多现成的模型可以使用。以下是一些常用的深度学习模型&#xff0c;适用于不同的机器视觉任务&#xff0c;包括物体检测、图像分类和分割等。 使用示例 在 OpenCvSharp 中加载和使用这些模型的基本示例&…
阅读更多...
【生成模型之七】Classifier-free diffusion guidance

【生成模型之七】Classifier-free diffusion guidance

论文&#xff1a;classifier-free diffusion guidance 一、Background 分类器引导是一种最近引入的方法&#xff0c;用于在训练后的条件扩散模型中权衡样本丰富度和样本保真度&#xff0c;其思想与其他类型生成模型中的低温采样或截断相同。 分类器引导将扩散模型的分数估计…
阅读更多...
【LeetCode每日一题】——415.字符串相加

【LeetCode每日一题】——415.字符串相加

文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时空频度】九【代码实现】十【提交结果】 一【题目类别】 字符串 二【题目难度】 简单 三【题目编号】 415.字符串相加 四【题目描述】 给定两个字符…
阅读更多...
Why SAP TM?

Why SAP TM?

最近发现跟 SAP TM 的集成越来越多了&#xff0c;并且发现这模块还挺大&#xff0c;很难一下子理解。TM&#xff08;Transportation Management&#xff09;- 顾名思义就是“运输管理”。起初很难想象为啥 SAP 会浪费大量的时间和精力开发“运输管理”&#xff0c;从而只是为了…
阅读更多...
开源鸿蒙 5.0 正式版发布

开源鸿蒙 5.0 正式版发布

在2024年的开放原子开发者大会上&#xff0c;开源鸿蒙5.0版本正式发布啦&#xff01;这个版本是一个比较大的升级&#xff0c;性能和功能都上了一个新台阶&#xff0c;让我们一起来看看都有哪些亮点。 首先&#xff0c;开源鸿蒙这个项目&#xff0c;从最初的700万行代码&#x…
阅读更多...
直流有刷电机多环控制(PID闭环死区和积分分离)

直流有刷电机多环控制(PID闭环死区和积分分离)

直流有刷电机多环控制 提高部分-第8讲 直流有刷电机多环控制实现(1)_哔哩哔哩_bilibili PID模型 外环的输出作为内环的输入&#xff0c;外环是最主要控制的效果&#xff0c;主要控制电机的位置。改变位置可以改变速度&#xff0c;改变速度是受电流控制。 实验环境 【 &…
阅读更多...
Odrive源码分析(四) 位置爬坡算法

Odrive源码分析(四) 位置爬坡算法

Odrive中自带一个简单的梯形速度爬坡算法&#xff0c;本文分析下这部分代码。 代码如下&#xff1a; #include <cmath> #include "odrive_main.h" #include "utils.hpp"// A sign function where input 0 has positive sign (not 0) float sign_ha…
阅读更多...
电视大全 1.3.8|汇聚多频道资源，秒切换流畅播放

电视大全 1.3.8|汇聚多频道资源，秒切换流畅播放

电视大全TV版是一款功能丰富的TV端直播软件&#xff0c;由悠兔电视的同一开发者打造。最新版本更新了更多频道&#xff0c;包括央视、卫视和地方频道等&#xff0c;提供了多线路流畅播放体验&#xff0c;并支持节目回看、线路选择、开机自启等功能。该应用免登录且无购物频道&a…
阅读更多...
JAVAweb学习日记（二）JavaScript

JAVAweb学习日记（二）JavaScript

一、概念 二、JavaScript引入方式 三、JavaScript书写语法 输出语句&#xff1a; 变量&#xff1a; 数据类型、运算符、流程控制语句&#xff1a; 数据类型&#xff1a; 运算符&#xff1a; 字符串如果是 数字字符构成&#xff0c;先把读到的数字转为数字类型&#xff0c;后续…
阅读更多...
深圳龙岗戴尔dell r730xd服务器故障维修

深圳龙岗戴尔dell r730xd服务器故障维修

深圳龙岗一台DELL POWEREDGE R730XD服务器系统故障问题处理&#xff1a; 1&#xff1a;客户工厂年底产线整改&#xff0c;时不时的会意外断电&#xff0c;导致服务器也频繁停机&#xff0c; 2&#xff1a;多次异常停机后导致服务器开机后windows server系统无法正常启动了&…
阅读更多...
Ansible 批量管理华为 CE 交换机

Ansible 批量管理华为 CE 交换机

注&#xff1a;本文为 “Ansible 管理华为 CE 交换机” 相关文章合辑。 使用 CloudEngine - Ansible 批量管理华为 CE 交换机 wsf535 IP 属地&#xff1a;贵州 2018.02.05 15:26:05 总体介绍 Ansible 是一个开源的自动化运维工具&#xff0c;AnsibleWorks 成立于 2012 年&a…
阅读更多...
2024年Python最新下载安装教程，附详细图文，持续更新

2024年Python最新下载安装教程，附详细图文，持续更新

大家好&#xff0c;我是Python老安&#xff0c;今天为大家带来的是Windows Python3下载、安装教程&#xff0c;适用于 Python3 所有版本&#xff0c;包括 Python3.7,Python33.8,Python33.10 等版本。希望对大家有所帮助 Python目前已支持所有主流操作系统&#xff0c;在Linux,…
阅读更多...
《点点之歌》“意外”诞生记

《点点之歌》“意外”诞生记

世界是“点点”的&#xff0c;“点点”是世界的。 (笔记模板由python脚本于2024年12月23日 19:28:25创建&#xff0c;本篇笔记适合喜欢诗文的coder翻阅) 【学习的细节是欢悦的历程】 Python 官网&#xff1a;https://www.python.org/ Free&#xff1a;大咖免费“圣经”教程《 …
阅读更多...
网络安全检测

网络安全检测

实验目的与要求 (1) 帮助学生掌握木马和入侵的防护和检测方法、提高学习能力、应用能力和解决实际问题的能力。 (2) 要求学生掌握方法, 学会应用软件的安装和使用方法, 并能将应用结果展示出来。 实验原理与内容 入侵检测是通过对计算机网络或计算机系统中若干关键点收集信…
阅读更多...
c++------------------函数

c++------------------函数

函数定义 语法格式 函数定义包括函数头和函数体。函数头包含返回类型、函数名和参数列表。函数体是用花括号{}括起来的代码块&#xff0c;用于实现函数的功能。例如&#xff0c;定义一个计算两个整数之和的函数&#xff1a; int add(int a, int b) {return a b; }这里int是返回…
阅读更多...
Java WEB：从起源到现代的传奇之旅

Java WEB：从起源到现代的传奇之旅

Java Web 起源于上世纪 90 年代&#xff0c;随着网络和浏览器的飞速发展&#xff0c;Java 为应对动态处理网页的需求&#xff0c;推出了 Servlet 技术。 1. Servlet 出现之前 在 Servlet 出现之前&#xff0c;用户请求主要是静态资源&#xff0c;如 html、css 等。此时的网络…
阅读更多...
最新文章

Copyright @ 2022~2023