每日一题（根据二叉树创建字符串，二叉树层序遍历，二叉树的层序遍历 II）

雪芙花

发布于 2022-10-31 11:01:21

1540

发布于 2022-10-31 11:01:21

文章被收录于专栏：雪芙花

持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第20天，点击查看活动详情

一：根据二叉树创建字符串

题目介绍：（题目链接）

代码：

class Solution {
public:
    string tree2str(TreeNode* root) {
         string ss;
         treecopy(root,ss);
         return ss;
    }
    void treecopy(TreeNode* root,string&amp; str) //传引用减少构造
    {
        if(root == nullptr)
        return ;

        str+= to_string(root->val);

        if(root->left || root -> right)
        {
            str+="(";
           treecopy(root->left,str);
            str+=")";
        }

        if(root->right)
    {
        str+="(";
           treecopy(root->right,str);
            str+=")";
    }
    }
};

思路：

利用的是前序遍历

注意：

左子树和右子树的判断条件： 1. if(root->left || root -> right) （假如左子树或者右子树不为空，则执行左） 2. if(root->right) （只有当右子树不为空时，执行右分支）
to_string的利用
void treecopy(TreeNode* root,string& str) （传引用减少构造）

二：二叉树层序遍历

题目描述：（题目链接）

方法一：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vv;
         if(root ==nullptr)
         return  vv;

         queue<TreeNode*> q;
         q.push(root);
         int numsize =1;
         while(!q.empty())
         {
             //一层一层的遍历
             vector<int> v;
           for(int i=0;i<numsize;i++)
           {
               TreeNode* cur = q.front();
               q.pop();
               v.push_back(cur->val);

               if(cur->left)
               q.push(cur->left);
               if(cur->right)
               q.push(cur->right);
           }
           vv.push_back(v);
           numsize = q.size();
           }
           return vv;

思路：

记录当前层数的个数，一层一层的遍历
利用了队列先进先出的特性

注意事项：

注意队列函数的使用： q.front() 取出队头的数据 q,back() 取队尾的数据（需要注意是的栈只能取队尾的数据，不能取对头的）
注意for循环的使用和numsize的更新，for(int i=0;i<numsize;i++)， numsize = q.size();

方法二：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vv;
         if(root ==nullptr)
         return  vv;

         queue<TreeNode*> q;
         q.push(root);
         int numsize =1;
         while(!q.empty())
         {
           
             TreeNode* cur = q.front(); //取出队列的头
             v.push_back(cur->val);
             q.pop();
             numsize--;

             if(cur->left)
             q.push(cur->left);
             if(cur->right)
             q.push(cur->right);

             if(numsize==0)
             {
                 vector<int> tem =v;
                 v.clear();
                 vv.push_back(tem);
                 numsize = q.size();
             }
         }
         return vv;
    }
};

三：二叉树的层序遍历 II

题目描述：（题目链接）

代码：

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
         vector<vector<int>> vv;
         if(root ==nullptr)
         return  vv;

         queue<TreeNode*> q;
         q.push(root);
         int numsize =1;
         while(!q.empty())
         {
             //一层一层的遍历
             vector<int> v;
           for(int i=0;i<numsize;i++)
           {
               TreeNode* cur = q.front();
               q.pop();
               v.push_back(cur->val);

               if(cur->left)
               q.push(cur->left);
               if(cur->right)
               q.push(cur->right);
           }
           numsize =q.size();
           vv.push_back(v);
         }
         reverse(vv.begin(),vv.end());
         return vv;
    }
};