【C++】二叉树之力扣经典题目1——详解二叉树的递归遍历，二叉树的层次遍历

如有错误，欢迎指正。
如有不理解的地方，可以私信问我。

---

题目1：根据二叉树创建字符串

点击进入题目链接——>力扣–根据二叉树创建字符串

题目

实例

思路与解析

题目的要求：二叉树已给出，我们需要采用前序遍历的方式，遍历二叉树，空节点用()表示
即用()标识左右子树，但是结果需要省略不必要的空括号对，并把遍历的结果放在字符串中，最后返回的是字符串。

思路解析：这道题是二叉树层序遍历的变形，前序遍历—根，左子树，右子树—采用递归，我们主要解决的是空括号对的省略问题，明确什么时候需要省略。

步骤：

• 如果是空树就直接返回空字符串
• 创建存放前序遍历结果的字符串要将整数转换成字符串,才能插入到字符串对象中
• 我们可以使用递归的方法得到二叉树的前序遍历，并在递归时加上额外的括号。用()标识左右子树，但是需要省略所有不必要的空括号对
• 如果当前节点有两个孩子，那我们在递归时，需要在两个孩子的结果外都加上一层括号；
• 如果当前节点没有孩子，那我们不需要在节点后面加上任何括号；
• 如果当前节点只有左孩子，那我们在递归时，只需要在左孩子的结果外加上一层括号，而不需要给右孩子加上任何括号；
• 如果当前节点只有右孩子，没有左孩子，那我们在递归时，需要先加上一层空的括号 ‘()’，‘()’ 表示左孩子为空，再对右孩子进行递归，并在结果外加上一层括号。
• 最后返回存放层序遍历结果的字符串

代码实现

 //思路：前序遍历---根，左子树，右子树---采用递归
class Solution {
public:string tree2str(TreeNode* root) {//1.如果是空树就返回空字符串if(root==nullptr){return string();}string str;//存放前序遍历结果的字符串//【根】str+=to_string(root->val);//要将整数转换成字符串//用()标识左右子树，但是需要省略所有不必要的开括号对//【左子树】//2.左子树不为空，所以我们需要标示左子树if(root->left){str+="(";//字符串+=用""或者‘’都可以str+=tree2str(root->left);str+=')';}else if(root->right)//3.如果左子树为空，右子树不为空，根据示例2，左子树为空，()不能省略，我们就手动加上{str+="()";}//【右子树】//4.对右子树的处理,我们需要标识右子树，从示例1中得，右子树为空，不需要加上()if(root->right){str+='(';str+=tree2str(root->right);str+=')';}return str;}
};

题目2：二叉树的层序遍历

点击进入题目链接——>力扣—二叉树的层序遍历

题目

思路与解析

思路：这道题考查二叉树的层序遍历，是层序遍历的变形，与普通的层序遍历不同的是，这道题的函数要求我们返回一个二维数组，所以我们需要先创建一个二维数组，二维数组中的一维数组分别存放二叉树每层的数据，根据题目的实例，我们要一层一层的遍历，将每层的遍历分别放在一维数组中，并利用队列的帮助进行层序遍历。接下来我们利用一个变量levelSize，这样可以准确的分开每层的数据，分别放在一维数组中。

代码实现

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> vv;//构建二维数组queue<TreeNode*> q;//存放二叉树结点的队列int levelSize=0;//每层的的结点个数if(root){q.push(root);levelSize=1;}while(!empty(q)){//构建一维数组，分别存放每层遍历的结果,一次循环结束后就push进二维数组vector<int> v;//levelSiz记录当前层的数据个数while(levelSize--)//关键思路：保证层序遍历{TreeNode* front=q.front();//保留队头结点地址q.pop();//出队头结点v.push_back(front->val);//将每层拿到的数据放进一维数组//push左子树if(front->left){q.push(front->left);}//push右子树if(front->right){q.push(front->right);}}levelSize=q.size();//将levelSize更改成当前成的数据个数vv.push_back(v);//将一维数组v（分别存放这每层的数据）push进二维数组vv中}return vv;}
};

变化：给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）点击进入题目：二叉树层序遍历II

解决方法：得到从上自下的层序遍历的二维数组后，用reverse函数，将二维数组中的内容翻转一下即可。