【LeetCode二叉树进阶题目】606. 根据二叉树创建字符串,102. 二叉树的层序遍历,107. 二叉树的层序遍历 II

本文主要是介绍【LeetCode二叉树进阶题目】606. 根据二叉树创建字符串,102. 二叉树的层序遍历,107. 二叉树的层序遍历 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

二叉树进阶题目

  • 606. 根据二叉树创建字符串
    • 解题思路及实现
  • 102. 二叉树的层序遍历
    • 解题思路及实现
  • 107. 二叉树的层序遍历 II
    • 解题思路及实现

606. 根据二叉树创建字符串

描述

给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串。

空节点使用一对空括号对 “()” 表示,转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例在这里插入图片描述

输入:root = [1,2,3,4]
输出:“1(2(4))(3)”
解释:初步转化后得到 “1(2(4()())())(3()())” ,但省略所有不必要的空括号对后,字符串应该是"1(2(4))(3)" 。

在这里插入图片描述

输入:root = [1,2,3,null,4]
输出:“1(2()(4))(3)”
解释:和第一个示例类似,但是无法省略第一个空括号对,否则会破坏输入与输出一一映射的关系。

解题思路及实现

在这里插入图片描述

class Solution {
public:string tree2str(TreeNode* root) {if(root == nullptr)return string();string str;str+=to_string(root->val);if(root->left){str+='(';str+=tree2str(root->left);str+=')';}else if(root->right)//走到这里,左一定为空{str+="()";}if(root->right){str+='(';str+=tree2str(root->right);str+=')';}return str;}
};

102. 二叉树的层序遍历

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

示例
在这里插入图片描述

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]

解题思路及实现

在这里插入图片描述

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> q;vector<vector<int>> vv;int LevelSize=0;if(root){q.push(root);LevelSize=1;}while(!q.empty()){vector<int> v;//一层一层出while(LevelSize--){TreeNode* front=q.front();q.pop();v.push_back(front->val);if(front->left)q.push(front->left);if(front->right)q.push(front->right);} vv.push_back(v);//当前一层出完了,下一层都进队列了,那q.size()就是下一层数据数LevelSize=q.size();}return vv;}
};

107. 二叉树的层序遍历 II

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

示例
在这里插入图片描述

输入:root = [3,9,20,null,null,15,7]
输出:[[15,7],[9,20],[3]]

解题思路及实现

这道题其实就是上面的变形,大家应该有这个思路。把结果翻转一下就好了。

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {queue<TreeNode*> q;vector<vector<int>> vv;int LevelSize=0;if(root){q.push(root);LevelSize=1;}while(!q.empty()){vector<int> v;//一层一层出while(LevelSize--){TreeNode* front=q.front();q.pop();v.push_back(front->val);if(front->left)q.push(front->left);if(front->right)q.push(front->right);} vv.push_back(v);//当前一层出完了,下一层都进队列了,那q.size()就是下一层数据数LevelSize=q.size();}reverse(vv.begin(),vv.end());return vv;}
};

这篇关于【LeetCode二叉树进阶题目】606. 根据二叉树创建字符串,102. 二叉树的层序遍历,107. 二叉树的层序遍历 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/418253

相关文章

Macos创建python虚拟环境的详细步骤教学

《Macos创建python虚拟环境的详细步骤教学》在macOS上创建Python虚拟环境主要通过Python内置的venv模块实现,也可使用第三方工具如virtualenv,下面小编来和大家简单聊聊... 目录一、使用 python 内置 venv 模块(推荐)二、使用 virtualenv(兼容旧版 P

Linux lvm实例之如何创建一个专用于MySQL数据存储的LVM卷组

《Linuxlvm实例之如何创建一个专用于MySQL数据存储的LVM卷组》:本文主要介绍使用Linux创建一个专用于MySQL数据存储的LVM卷组的实例,具有很好的参考价值,希望对大家有所帮助,... 目录在Centos 7上创建卷China编程组并配置mysql数据目录1. 检查现有磁盘2. 创建物理卷3. 创

golang float和科学计数法转字符串的实现方式

《golangfloat和科学计数法转字符串的实现方式》:本文主要介绍golangfloat和科学计数法转字符串的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望... 目录golang float和科学计数法转字符串需要对float转字符串做处理总结golang float

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

python进行while遍历的常见错误解析

《python进行while遍历的常见错误解析》在Python中选择合适的遍历方式需要综合考虑可读性、性能和具体需求,本文就来和大家讲解一下python中while遍历常见错误以及所有遍历方法的优缺点... 目录一、超出数组范围问题分析错误复现解决方法关键区别二、continue使用问题分析正确写法关键点三

JSR-107缓存规范介绍

《JSR-107缓存规范介绍》JSR是JavaSpecificationRequests的缩写,意思是Java规范提案,下面给大家介绍JSR-107缓存规范的相关知识,感兴趣的朋友一起看看吧... 目录1.什么是jsR-1072.应用调用缓存图示3.JSR-107规范使用4.Spring 缓存机制缓存是每一

MySQL 字符串截取函数及用法详解

《MySQL字符串截取函数及用法详解》在MySQL中,字符串截取是常见的操作,主要用于从字符串中提取特定部分,MySQL提供了多种函数来实现这一功能,包括LEFT()、RIGHT()、SUBST... 目录mysql 字符串截取函数详解RIGHT(str, length):从右侧截取指定长度的字符SUBST

Python将字符串转换为小写字母的几种常用方法

《Python将字符串转换为小写字母的几种常用方法》:本文主要介绍Python中将字符串大写字母转小写的四种方法:lower()方法简洁高效,手动ASCII转换灵活可控,str.translate... 目录一、使用内置方法 lower()(最简单)二、手动遍历 + ASCII 码转换三、使用 str.tr

Java如何用乘号来重复字符串的功能

《Java如何用乘号来重复字符串的功能》:本文主要介绍Java使用乘号来重复字符串的功能,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java乘号来重复字符串的功能1、利用循环2、使用StringBuilder3、采用 Java 11 引入的String.rep

Java 如何创建和使用ExecutorService

《Java如何创建和使用ExecutorService》ExecutorService是Java中用来管理和执行多线程任务的一种高级工具,可以有效地管理线程的生命周期和任务的执行过程,特别是在需要处... 目录一、什么是ExecutorService?二、ExecutorService的核心功能三、如何创建