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