26 将二叉树按照层级转化为链表（Convert Binary Tree to Linked Lists by Depth）

• • 1 题目
  • 2 解决方案
  • • 2.1 思路
    • 2.2 时间复杂度
    • 2.3 空间复杂度
  • 3 源码

题目：将二叉树按照层级转化为链表（Convert Binary Tree to Linked Lists by Depth）
描述：给一棵二叉树，设计一个算法为每一层的节点建立一个链表。也就是说，如果一棵二叉树有 D 层，那么你需要创建 D 条链表。

lintcode题号——242，难度——easy

样例1：

输入: {1,2,3,4}
输出: [1->null,2->3->null,4->null]
解释: 
        1
       / 
      2   3
     /
    4

样例2：

输入: {1,#,2,3}
输出: [1->null,2->null,3->null]
解释: 
    1
     
      2
     /
    3

  使用宽度优先搜索进行层级遍历，在每一层的for循环中将链表组合并保存头节即可。

  二叉树宽度优先搜索，遍历所有的节点，算法的时间复杂度为O(n)。

  使用了queue队列数据结构保存节点，算法的空间复杂度为O(n)。

细节：

1. 为了不单独特殊处理每层的头节点，可以使用一个dummyListNode（模拟头），然后将头节点当成普通节点处理，实际返回数据时，返回dummyListNode->next即可。

C++版本：

vector binaryTreeToLists(TreeNode* root) {
    // Write your code here
    vector result;
    if (root == nullptr)
    {
        return result;
    }

    queue nodeQueue;
    nodeQueue.push(root);
    while (!nodeQueue.empty())
    {
        ListNode * dummyListNode = new ListNode(0); // 新建一个虚拟头节点，避开头节点的处理问题
        ListNode * curListNode = dummyListNode; // 用于遍历的Node
        int size = nodeQueue.size();
        for (int i = 0; i < size; i++)
        {
            TreeNode * curTreeNode = nodeQueue.front();
            nodeQueue.pop();
            curListNode->next = new ListNode(curTreeNode->val);
            curListNode = curListNode->next;
            if (curTreeNode->left != nullptr)
            {
                nodeQueue.push(curTreeNode->left);
            }
            if (curTreeNode->right != nullptr)
            {
                nodeQueue.push(curTreeNode->right);
            }
        }
        result.push_back(dummyListNode->next); // 保存的是虚拟头节点的next指针
    }

    return result;
}