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

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

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

• 题目介绍：（题目链接）

• 代码：

代码语言：javascript复制

class Solution {
public:
    string tree2str(TreeNode* root) {
         string ss;
         treecopy(root,ss);
         return ss;
    }
    void treecopy(TreeNode* root,string& 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. 左子树和右子树的判断条件 ： 1. if(root->left || root -> right) （假如左子树或者右子树不为空，则执行左） 2. if(root->right) （只有当右子树不为空时，执行右分支）
2. to_string的利用
3. void treecopy(TreeNode* root,string& str) （传引用减少构造）

二：二叉树层序遍历

题目描述：（题目链接）

• 方法一：

代码语言：javascript复制

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;

• 思路：

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

• 注意事项：

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

• 方法二：

代码语言：javascript复制

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

• 题目描述： （题目链接）

• 代码：

代码语言：javascript复制

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

• 思路：

reverse一下就得到了

二叉树 编程算法

0 人点赞