题解 | #求二叉树的层序遍历#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
方法一：首先是建立两个队列，然后队列A是装队列B的子节点，也就是下一层的结点，然后在把A中的结点传到B中，就可以接着下一层输出层次遍历的结果
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        queue<TreeNode*>q1;
         queue<TreeNode*>q2;//两个队列
         vector<int>res;
         vector<vector<int>>res2;
          if(root==NULL)
        {
            return res2;
        }
         q1.push(root);
         while(!q1.empty())
         {
            while(!q1.empty())
            {
                TreeNode*node=q1.front();
                q1.pop();
                res.push_back(node->val);
                if(node->left)
                {
                    q2.push(node->left);
                }
                if(node->right)
                {
                    q2.push(node->right);
                }
            }
            res2.push_back(res);
            res.clear();
            while(!q2.empty())
            {
                q1.push(q2.front());
                q2.pop();
            }
         }
    return res2;
    }
};
方法二：非递归，用一个队列，设置一个变量来存同一层的结点的数量，然后用for循环来将一层的结点放到vector<vector<int>>对应的位置上。
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        vector<vector<int>>res2;
        if(root==NULL)
        {
            return res2;
        }
        vector<int>res;
        queue<TreeNode*>q;
        TreeNode*node=NULL;
        q.push(root);
        while(!q.empty())
        {
            
            int n=q.size();
            for(int i=0;i<n;i++)
            {
                node=q.front();
                res.push_back(node->val);
                q.pop();
                if(node->left)
                {
                    q.push(node->left);
                }
                if(node->right)
                {
                    q.push(node->right);
                }
            }
            res2.push_back(res);
            res.clear();
        }
         return res2;
    
    }
};
方法三：递归法
class Solution {
public:
    void process(vector<vector<int> >&res2,TreeNode* root,int depth)
    {
        if(root)
        {
            if(res2.size()<depth)
            {
                 res2.push_back(vector<int>{});
            }
           
            res2[depth-1].push_back(root->val);
        }
        else {
        return ;
        }
        process(res2,root->left,depth+1);
        process(res2,root->right,depth+1);
    }


    vector<vector<int> > levelOrder(TreeNode* root) {
       vector<vector<int> >res2;
       if(root==NULL)
       {
        return res2;
       }
      process(res2,root,1);
        return res2;
    
    }
};