【LeetCode二叉树进阶题目】606，102，107

本文主要是介绍【LeetCode二叉树进阶题目】606，102，107，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树进阶题目

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;}
};