力扣102题：二叉树的层序遍历

力扣102题：二叉树的层序遍历

题目描述

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

输入输出样例

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

输入：root = [1]
输出：[[1]]

输入：root = []
输出：[]

解法1，使用队列利用迭代的方式

vector<vector<int>> levelOrder(TreeNode* root) 
{
    
    vector<vector<int>>res;
    if(!root)
    {
    
        return res;
    }
    //建立队列
    queue<TreeNode *>que;
    que.push(root);
    vector<int>tempList;

    while(!que.empty())
    {
    
        int length=que.size();
        res.push_back({
    });

        for(int i=0;i<length;i++)
        {
    
            TreeNode * temp=que.front();
            que.pop();
            // cout<<temp->val<<" ";
            res.back().push_back(temp->val);
        
            if(temp->left)
            {
    
                que.push(temp->left);
            }
            if(temp->right)
            {
    
                que.push(temp->right);
            }
        }
    }
    return res;
}

解法二，使用递归的方式进行

vector<vector<int>>nums;
//使用递归的方法进行解决

void dns(TreeNode *root,int lever)
{
    
    if(!root)
    {
    
        return;
    }
    if(nums.size()==lever)
    {
    
        nums.push_back({
    });
    }
    nums[lever].push_back(root->val);

    dns(root->left,lever+1);
    dns(root->right,lever+1);
}


 vector<vector<int>> levelOrder2(TreeNode* root) 
 {
    
    dns(root,0);
    return nums;
 }