Interview question 04.03 Specific depth node linked list (medium)

Interview questions 04.03. Specific depth node list

Given a binary tree , Design an algorithm , Create a linked list containing all nodes at a certain depth （ such as , If the depth of a tree is D, Then create D A linked list ）. Returns an array containing a linked list of all depths .

Example ：

 Input ：[1,2,3,4,5,null,7,8]

        1
       /  \ 
      2    3
     / \    \ 
    4   5    7
   /
  8

 Output ：[[1],[2,3],[4,5,7],[8]]

Ideas

It can be seen that the linked list is established layer by layer , It's natural to think of using queues to traverse , Pop up elements one layer at a time , We create the node of the linked list according to the value of the element . However, the chain header node itself will participate in backward traversal , So we also need to create a virtual head node before the loop of the first layer, pointing to the real head node

Source code

class Solution {
    
public:
    vector<ListNode*> listOfDepth(TreeNode* tree) {
    
        vector<ListNode*> v;
        if (tree == nullptr) {
    
            return v;
        }
        queue<TreeNode*> queue;
        queue.push(tree);
        
        while (!queue.empty()) {
    
            int size = queue.size();
            ListNode* virtual_head = new ListNode();//  Create a virtual head node to point to the real head node 
            ListNode* head = virtual_head;//  Create a header node , The follow-up will continue to move forward 
            for (int i=0; i<size; i++) {
    
                TreeNode* node = queue.front();
                queue.pop();
                head->next = new ListNode(node->val);//  Create a linked list node with the same value , And let the head node point to it 
                head = head->next;//  Head node backward 
                if (node->left) {
    
                    queue.push(node->left);//  Push the 
                }
                if (node->right) {
    
                    queue.push(node->right);//  Push the 
                }
            }
            v.push_back(virtual_head->next);//  Create a linked list one layer at a time , Push the head node of the linked list into vector
        }
        return v;

    }
};