二叉树进阶oj题

1. 二叉树创建字符串。

给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
要用括号分别括住左右子树
空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
链接：力扣（LeetCode）

省略：
左右都为空
右子树为空，左子树不为空
若仅左为空，不省略
前序遍历

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;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

问题点：return str；是传值返回
解决：写一个子函数，用str的引用传参

 

2. 二叉树的分层遍历1。

链接

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

难点：
想办法去区分是否是同一层的结点
控制一层一层出——levelsize

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 (size_t i = 0; i < levelSize; ++i)
            {
   
                //出的是结点的指针，存的也是结点的指针
                //树的指针
                TreeNode* front = q.front();
                q.pop();//出队列，出的是队列中存的值，树结点的指针已经被保存了
              
                  //将队列中的值尾插进v中
                v.push_back(front->val);

               //下一层的进队列
                 if (front->left)
                {
   
                    q.push(front->left);
                }

                if (front->right)
                {
   
                    q.push(front->right);
                }
            }
            vv.push_back(v);//二维数组，一层一层
            
            //当前层出完了，下一层都进队列，队列的size就是下一层的数据个数
            levelSize = q.size();
        }
         return vv;
    }
   
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

还有另外一种思路：双队列
1.存结点指针
2.存层数

 

3. 二叉树的分层遍历2。

链接

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

逆置

reverse（vv.begin(),vv.end());
class Solution 
1