leetcode 链接：特定深度节点链表

题目

给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
示例：

输入：[1,2,3,4,5,null,7,8]
        1
       /  \ 
      2    3
     / \    \ 
    4   5    7
   /
  8
输出：[[1],[2,3],[4,5,7],[8]]

解答 & 代码

层序遍历二叉树（广度优先搜索）即可，问题是如何判断节点是否属于新的一层，需要建立新的链表？
想法：

• 初始时，将树的根节点压入队列 nodeQ

• 如果 nodeQ 不为空，则循环：

  • 当前队列 nodeQ 中存储的所有节点是同一层的，应该将这些节点的值存储在同一个链表中
  • 因此，得到 nodeQ.size() ，代表二叉树该层的节点数，遍历队列 nodeQ 中存储的这些节点
    • 对于当前节点，如果存在左右子树，则压入队列（因此上面这个内循环应该用一开始的 size 来作为循环范围，而不能用队列为空作为循环结束条件）
    • 建立新的链表节点，插入当前层的链表末端

  • 将当前层的链表的实际头结点压入数组尾部

    /**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    * };
    */
    /**
    * Definition for singly-linked list.
    * struct ListNode {
    *     int val;
    *     ListNode *next;
    *     ListNode(int x) : val(x), next(NULL) {}
    * };
    */
    class Solution {
    public:
    vector<ListNode*> listOfDepth(TreeNode* tree) {
       vector<ListNode*> treeLists;    // 存储二叉树各层链表头结点的数组
       queue<TreeNode*> nodeQ;            // 队列，用于二叉树层序遍历（广度优先搜索）
       nodeQ.push(tree);                // 将根节点压入队列
       while(!nodeQ.empty())            // 层序遍历二叉树节点
       {
           ListNode* dummyHead = new ListNode(0);    // 二叉树当前层链表的虚拟头节点
           ListNode* preNode = dummyHead;
           int levelSize = nodeQ.size();            // 二叉树当前层节点数
           for(int i = 0; i < levelSize; ++i)        // 遍历二叉树当前层所有节点
           {
               TreeNode* cur = nodeQ.front();        // 取一个节点
               nodeQ.pop();
               if(cur->left != NULL)                // 如果存在左子树，则压入队列
                   nodeQ.push(cur->left);
               if(cur->right != NULL)                // 如果存在右子树，则压入队列
                   nodeQ.push(cur->right);
    
               ListNode* curNode = new ListNode(cur->val);    // 为当前树节点的值建立链表节点
               preNode->next = curNode;                    // 将当前节点接入当前层链表尾部
               preNode = curNode;
           }
           treeLists.push_back(dummyHead->next);            // 将当前层链表的实际头节点压入数组中
       }
       return treeLists;
    }
    };
    

    执行结果： ``` 执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 53.10% 的用户 内存消耗：8 MB, 在所有 C++ 提交中击败了 32.05% 的用户 ```