Question 102: sequence traversal of binary tree

Power button 102 topic ： Sequence traversal of binary tree

Title Description

Give you the root node of the binary tree root , Returns the Sequence traversal . （ That is, layer by layer , Access all nodes from left to right ）.

I/o sample

 Input ：root = [3,9,20,null,null,15,7]
 Output ：[[3],[9,20],[15,7]]

 Input ：root = [1]
 Output ：[[1]]

 Input ：root = []
 Output ：[]

solution 1, Use queues to leverage iterations

vector<vector<int>> levelOrder(TreeNode* root) 
{
    
    vector<vector<int>>res;
    if(!root)
    {
    
        return res;
    }
    // Build queue 
    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;
}

Solution 2 , Use recursion

vector<vector<int>>nums;
// Use recursive method to solve 

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