image.png

思路：

  • 层次遍历二叉树
  • 每一层都建立链表
  • 为了不使用额外空间，所以采用cur_node->next = q.front() 这样的结构

    代码：

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     Node* left;
  7.     Node* right;
  8.     Node* next;
  10.     Node() : val(0), left(NULL), right(NULL), next(NULL) {}
  12.     Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
  14.     Node(int _val, Node* _left, Node* _right, Node* _next)
  15.         : val(_val), left(_left), right(_right), next(_next) {}
  16. };
  17. */
  19. class Solution {
  20. public:
  21.     Node* connect(Node* root) {
  22.         if (!root) {
  23.             return nullptr;
  24.         }
  26.         queue<Node*> q;
  27.         q.push(root);
  29.         while (!q.empty()) {
  30.             int cur_level_size = q.size();
  31.             for (int i = 0; i < cur_level_size; ++i) {
  32.                 Node* cur_node = q.front();
  33.                 q.pop();
  34.                 if (i != cur_level_size - 1) {
  35.                     cur_node->next = q.front();
  36.                 } else {
  37.                     cur_node->next = nullptr;
  38.                 }
  40.                 if (cur_node->left) q.push(cur_node->left);
  41.                 if (cur_node->right) q.push(cur_node->right);
  42.             }
  43.         }
  45.         return root;
  46.     }
  47. };