Welcome to 9ilk's Code World

       

(๑•́ ₃ •̀๑) 个人主页:        9ilk

(๑•́ ₃ •̀๑) 文章专栏：     数据结构 

---

从本篇文章开始，博主将分享一些结合二叉树的进阶算法题。

---

🏠 根据二叉树创建字符串

📌 题目内容

根据二叉树创建字符串

📌 题目解析

本题有几个点需要注意：

• 题目需要我们按前序遍历去构建字符串，遇到为空的节点用()表示。
• 在不破坏映射的前提下，空括号是可以省略的。比如：当右子树不为空时，左子树为空的时候空括号不能省略，因为这样就分不清这个节点是连在根的左子树还是右子树了。

📌 算法分析

1. 我们将PreOrder()看作一个具有帮我们分别将根-左子树-右子树的值添加进字符串的功能的函数，按照这个顺序进行递归。

2.什么时候需要加括号：a.当右子树不为空的时候，左子树无论是否有节点都是要加上空括号的，

b.当右子树为空时，右子树的空括号是可以省略的。

3.递归终止条件：遇到空节点并停止递归。

4.在C++中添加字符到字符串中，我们直接调用+=就方便许多了。

参考代码：

  void PreOrder(string& str, TreeNode* root){  //叶子节点的括号才能忽略if (root == nullptr)return;// str += to_string(root->val);//访问左子树 右子树和左子树不为空都需要加括号 if (root->left || root->right) //非叶子节点的左为空不能忽略{   str += '(';PreOrder(str, root->left);str += ')';}//访问右子树 if (root->right){str += '(';PreOrder(str,root->right);str += ')';}}string tree2str(TreeNode* root){string str;PreOrder(str, root);return str;}

---

🏠 二叉树的层序遍历II

📌 题目内容

二叉树的层序遍历II

📌 题目解析

• 题目要求我们返回的是一个二维数组，二维数组内的每一个一维数组是这个二叉树每一层的结点
• 最后要我们返回的是从最后一层到第一层的二维数组，但是每一层节点的顺序是从左到右。

📌 算法分析

✏️ 思路一：

1. 我们二叉树的层序遍历是借助一个队列，利用“一父带两娃”的思想(即一个父亲入队的时候，它的两个孩子也一起入队)实现。

2.本道题重点是采用层序遍历的思想，我们无法具体划分出每个节点归属的层次。

3.我们可以再开一个队列，用来存每个节点所对应的层次。当一个父亲(层次是h)入队时，那他的两个孩子对应的层次就是h+1；同时当一个节点出队时，他对应高度也对应出。

4.为了效率，我们可以先计算总的高度，提前开好二维数组所需要的层数；但是注意resize之后就不要调用push_back，因为push_back会新开空间。

5.我们按上面流程得到的是从上到下的层序遍历，从下往上我们可以使用reverse算法进行逆置。

参考代码：

   //求高度int height(TreeNode* root){if (root == nullptr)return 0;int left = height(root->left);int right = height(root->right);return left > right ? left + 1 :right + 1;}vector<vector<int>> levelOrder(TreeNode* root){vector<vector<int>> vv;if(root == nullptr)return vv;int Height = height(root);//预先开好层数空间 vv.resize(Height);queue<TreeNode*> treeq;queue<int> levelq;levelq.push(1);//根节点是第一层treeq.push(root);vv[0].push_back(root->val);while(!treeq.empty()){TreeNode* front = treeq.front();treeq.pop();           int levelsize = levelq.front();levelq.pop();if(front->left)  //一父带两娃的同时也push对应高度{treeq.push(front->left);levelq.push(levelsize+1);vv[levelsize].push_back(front->left->val); //push进对应层数的数组}  if(front->right){treeq.push(front->right);levelq.push(levelsize+1);vv[levelsize].push_back(front->right->val);}  }reverse(vv.begin(),vv.end());return vv;}

✏️ 思路二：

1.了解思路一后，我们发现思路一维护每个结点的层数比较麻烦，我们能否另寻他路，一口气把每层的结点push进数组里？

2.我们用levelsize表示每一层结点个数，假设有颗满二叉树，当根结点入队时顺便此时他的左右结点也顺便入队，此时队列中结点的个数就是2，此时这两个结点对应层数就是2；类似地当第二层的两结点一父带两娃时，此时入队了4个结点，这一层也是有4个结点。因此，每次“一父带两娃”后队列内的结点个数就是他们对应的层数，利用这个levelsize进行一个循环，把这一层的结点都push进对应层的数组内。

动图演示：

参考代码：

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root){queue<TreeNode*> tq;vector<vector<int>> vv;if(root == nullptr)return vv;tq.push(root);int levelsize = 1; //层数表示了要“一父带两娃”的次数 也就是上一层带入的孩子总个数// vv.push_back(vector<int>({root->val}));vector<int> del = {root->val};vv.push_back(del);while(!tq.empty()) //也可以是levelsize ！= 0{vector<int> v;while(levelsize--) {TreeNode* front = tq.front();//一父带两娃    tq.pop();if(front->left){tq.push(front->left);v.push_back(front->left->val);  }if(front->right){tq.push(front->right);v.push_back(front->right->val);  }}levelsize = tq.size();if(v.size())vv.push_back(v);}reverse(vv.begin(),vv.end());return vv;}
};

---

完(๑¯ω¯๑)