👉根据二叉树创建字符串👈
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
思路：本道题就是前序遍历创建字符串，创建字符串时需要用括号将左右子树括起来。当左右子树都为空时，可以省略掉左右子树的括号。当左子树不为空，右子树为空时，可以省略掉右子树的括号。当左子树为空，右子树不为空时，左子树的括号不能省略掉。
class Solution { public: string tree2str(TreeNode* root) { if(root == nullptr) return string(); string str; str += to_string(root->val); // 左边不为空或者左边为空右边不为空，需要加括号 if(root->left || root->right) { str += '('; str += tree2str(root->left); str += ')'; } // 右边不为空，需要加括号 if(root->right) { str += '('; str += tree2str(root->right); str += ')'; } return str; } };
以上的解法还可以优化一下，因为返回值是string，会存在比较多的拷贝构造，我们可以通过引用和调用子函数的方式来优化。
class Solution { private: void _tree2str(TreeNode* root, string& str) { if(root == nullptr) return; str += to_string(root->val); if(root->left || root->right) { str += '('; str += tree2str(root->left); str += ')'; } if(root->right) { str += '('; str += tree2str(root->right); str += ')'; } } public: string tree2str(TreeNode* root) { string str; _tree2str(root, str); return str; } };
👉二叉树的层序遍历 I 和 II👈
二叉树的层序遍历 I
给你二叉树的根节点 root ，返回其节点值的层序遍历。 （即逐层地，从左到右访问所有节点）。
思路一：
首先定义一个队列q和当前层的节点个数levelSize = 0
当根节点root不为空时，根节点如队列q，且将levelSize设置为 1
当队列不为空时，while循环进行。while循环内部用for循环来控制出一层的节点，出的同时需要将所出节点的左右孩子也让入队列中（如果有的话）。
当for结束后，队列的size就是下一层的节点个数了。
while循环结合后，就能够得到二维数组了。
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> q; size_t levelSize = 0; if(root) { q.push(root); levelSize = 1; } vector<vector<int>> vv; while(!q.empty()) { vector<int> v; // 控制一层一层出 for(int i = 0; i < levelSize; ++i) { TreeNode* top = q.front(); v.push_back(top->val); q.pop(); if(top->left) q.push(top->left); if(top->right) q.push(top->right); } vv.push_back(v); // 当前层出完了,下一层的节点都进队列了,队列的size就是下一层的节点个数 levelSize = q.size(); } return vv; } };
思路二：
先申请一个队列q，如果根节点root不为空，根节点入队列
然后定义两个TreeNode*变量curend = root和nextend = nullptr，curend为当前层的最后一个节点，next是下一层的最后一个节点。
当队列不为空，while循环继续。队头所出的节点记为front，将front->val尾插到一位数组v中。然后front的左右孩子入队列（如果有的话），入的同时将nextend更新为最后入队列的节点。
当所出节点front等于当前层最后的节点curend时，说明当前层所有节点的值已经收集完毕，即可将一维数组v尾插到二维数组vv中。然后还需要做以下操作：清空一维数组v；准备收集下一层节点的值，更新当前层的最后一个节点curend = nextend；next置为空（可以不做，最好做）
while循环结束，二维数组vv存储的就是层序遍历的结果。
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> q; if(root) { q.push(root); } vector<vector<int>> vv; TreeNode* curend = root; // 当前层最后一个节点 TreeNode* nextend = nullptr; // 下一层最后一个节点 vector<int> v; while(!q.empty()) { TreeNode* front = q.front(); v.push_back(front->val); q.pop(); if(front->left) { q.push(front->left); nextend = front->left; } if(front->right) { q.push(front->right); nextend = front->right; } // 当front等于curend时,说明当前层所有节点的值已收集完毕 // 可以准备收集下一层节点的值 if(front == curend) { vv.push_back(v); v.clear(); // 清空一维数组 curend = nextend; // 更新curend } } return vv; } };
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> q; if(root) { q.push(root); } vector<vector<int>> vv; TreeNode* curend = root; // 当前层最后一个节点 TreeNode* nextend = nullptr; // 下一层最后一个节点 vector<int> v; while(!q.empty()) { TreeNode* front = q.front(); v.push_back(front->val); q.pop(); // 只要是下一层节点入了队列,就需要更新nextend为入队列的节点 if(front->left) { q.push(front->left); nextend = front->left; } if(front->right) { q.push(front->right); nextend = front->right; } // 当front等于curend时,说明当前层所有节点的值已收集完毕 // 可以准备收集下一层节点的值 if(front == curend) { vv.push_back(v); v.clear(); // 清空一维数组 curend = nextend; // 更新curend } } return vv; } };
注：以上两种方法还有用来求二叉树的最大宽度。
其实还有一种思路：双队列也可以解决这道题。一个队列存储节点，另一个队列存节点的所在层数，大家可以尝试一下。
二叉树的层序遍历 II
给你二叉树的根节点 root ，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
我们只需要将二叉树的层序遍历 I 中得到的二维数组vv反转一下就能够解决这道题了。
class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { queue<TreeNode*> q; size_t levelSize = 0; if(root) { q.push(root); levelSize = 1; } vector<vector<int>> vv; while(!q.empty()) { vector<int> v; // 控制一层一层出 for(int i = 0; i < levelSize; ++i) { TreeNode* top = q.front(); v.push_back(top->val); q.pop(); if(top->left) q.push(top->left); if(top->right) q.push(top->right); } vv.push_back(v); // 当前层出完了,下一层的节点都入队列了,队列的size就是下一层节点的个数 levelSize = q.size(); } reverse(vv.begin(), vv.end()); return vv; } };
