1. 题目描述

给定一个二叉树

  1. struct Node {
  2.   int val;
  3.   Node *left;
  4.   Node *right;
  5.   Node *next;
  6. }

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。

进阶：

  • 你只能使用常量级额外空间。

  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。


    示例：
    117.填充每个节点的下一个右侧节点指针 II - 图1
    输入：root = [1,2,3,4,5,null,7]
    输出：[1,#,2,3,#,4,5,7,#]
    解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），’#’ 表示每层的末尾。

    提示：

  • 树中的节点数小于 6000

  • -100 <= node.val <= 100

    2. 解题思路

    对于这道题目，我们可以对树进行层序遍历，树的层序遍历是基于广度优先遍历的，按照层的顺序进行遍历，我们需要舒适话一个队列queue，这个队列中保存着当前层的节点。

当队列不为空的时候就记录当前队列的的长度len，当遍历这一层的时候，修改这一层节点的 next 指针，这样就可以把每一层都组织成链表。

复杂度分析：

  • 时间复杂度：O(N)。其中N是树的节点数，我们需要遍历这棵树上所有的点，时间复杂度为 O(N)。
  • 空间复杂度：O(N)。其中N是树的节点数，我们需要初始化一个队列，它的长度最大不超过树的节点数。

    3. 代码实现

    ```javascript /**
    • // Definition for a Node.
    • function Node(val, left, right, next) {
    • this.val = val === undefined ? null : val;
    • this.left = left === undefined ? null : left;
    • this.right = right === undefined ? null : right;
    • this.next = next === undefined ? null : next;
    • }; */

/**

  • @param {Node} root
  • @return {Node} */ var connect = function(root) { if (!root) {
    1.  return null;
    } const queue = [root]; while (queue.length) {
    1.  const len = queue.length;
    2.  let last = null;
    3.  for (let i = 1; i <= len; ++i) {
    4.      let node = queue.shift();
    5.      if (node.left) {
    6.          queue.push(node.left);
    7.      }
    8.      if (node.right) {
    9.          queue.push(node.right);
    10.      }
    11.      if (i !== 1) {
    12.          last.next = node;
    13.      }
    14.      last = node;
    15.  }
    } return root; }; ```

    4. 提交结果

    image.png