以下题目更适合使用C++完成，难度也更大一些，所以放在这里。
文字解析能力有限，难理解的地方可以跟着代码画画图，或者看看官方题解。
606. 根据二叉树创建字符串 - 力扣（LeetCode）
难度简单
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例 1：
输入：root = [1,2,3,4]
输出："1(2(4))(3)"
解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。
示例 2：
输入：root = [1,2,3,null,4]
输出："1(2()(4))(3)"
解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。
提示：
- 树中节点的数目范围是
[1, 10^4] -1000 <= Node.val <= 1000
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: string tree2str(TreeNode* root) { } };
解析代码：
class Solution { public: // 这里的2有人当成to命名 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; } };
这段代码的缺陷就是传值返回，代价有点大，
改进就是写一个子函数去用引用返回，这里就不改了。
102. 二叉树的层序遍历 - 力扣（LeetCode）
难度中等
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { } };
解析代码：
以前用C语言讲的层序遍历：
数据结构与算法⑯(第四章_下)二叉树的层序遍历+判断完全二叉树+一道OJ_GR C的博客-CSDN博客
现在我们有STL就不用自己弄一个队列了，而且可以对比一下选C语言给的代码和选C++给的，
就能体会到C++的方便了，C++写：
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> q; int levelSize = 0; // 每一层的结点数量，因为要放在不同的vector中 if(root) { q.push(root); levelSize = 1; } vector<vector<int>> vv; while(!q.empty()) { vector<int> v; while(levelSize--) // 控制一层一层出 { TreeNode* front = q.front(); v.push_back(front->val); if(front->left) // 出完一个就入它的左右结点 { q.push(front->left); } if(front->right) { q.push(front->right); } q.pop(); } levelSize = q.size(); // 此时下一层的已入完，更新levelSize vv.push_back(v); } return vv; } };
107. 二叉树的层序遍历 II - 力扣（LeetCode）
难度中等
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { } };
解析代码：
这题写过上面的，直接复制上面的代码，最后加一句reverse：
class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { queue<TreeNode*> q; int levelSize = 0; // 每一层的结点数量，因为要放在不同的vector中 if(root) { q.push(root); levelSize = 1; } vector<vector<int>> vv; while(!q.empty()) { vector<int> v; while(levelSize--) // 控制一层一层出 { TreeNode* front = q.front(); v.push_back(front->val); if(front->left) // 出完一个就入它的左右结点 { q.push(front->left); } if(front->right) { q.push(front->right); } q.pop(); } levelSize = q.size(); // 此时下一层的已入完，更新levelSize vv.push_back(v); } reverse(vv.begin(),vv.end()); return vv; } };
236. 二叉树的最近公共祖先 - 力扣（LeetCode）
难度中等
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点5和节点4的最近公共祖先是节点5 。
因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2 输出：1
提示：
- 树中节点数目在范围
[2, 105]内。 -109 <= Node.val <= 109- 所有
Node.val互不相同。 p != qp和q均存在于给定的二叉树中。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { } };
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145（中）：https://developer.aliyun.com/article/1521950
