117.填充每个节点的下一个右侧节点指针II

链接：117.填充每个节点的下一个右侧节点指针II
难度：Medium
标签：树、深度优先搜索、广度优先搜索、链表、二叉树
简介：给定一个二叉树，填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

题解 1 - javascript

• 编辑时间：2020-09-28
• 执行用时：120ms
• 内存消耗：42.8MB
• 编程语言：javascript
• 解法介绍：层序遍历。

var connect = function (root) {
  if (root === null) return root;
  const queue = [root];
  let size = 1;
  while (queue.length !== 0) {
    const node = queue.shift();
    node.left && queue.push(node.left);
    node.right && queue.push(node.right);
    if (--size === 0) {
      node.next = null;
      size = queue.length;
    } else {
      node.next = queue[0];
    }
  }
  return root;
};

题解 2 - typescript

• 编辑时间：2021-08-14
• 执行用时：96ms
• 内存消耗：43.6MB
• 编程语言：typescript
• 解法介绍：层序遍历。

function connect(root: Node | null): Node | null {
  if (root === null) return null;
  const q: Node[] = [root];
  let size = 1;
  while (q.length) {
    const node = q.shift()!;
    node.left && q.push(node.left);
    node.right && q.push(node.right);
    if (--size === 0) {
      size = q.length;
      for (let i = 0; i < size; i++) {
        q[i].next = i === size - 1 ? null : q[i + 1];
      }
    }
  }
  return root;
}

题解 3 - python

• 编辑时间：2023-11-03
• 执行用时：56ms
• 内存消耗：17.01MB
• 编程语言：python
• 解法介绍：层序遍历。

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root: return root
        q = deque([root])
        size = 1
        while q:
            cur = q.popleft()
            size -= 1
            if cur.left: 
                if size != len(q): q[-1].next = cur.left
                q.append(cur.left)
            if cur.right: 
                if size != len(q): q[-1].next = cur.right
                q.append(cur.right)
            if size == 0: size = len(q)
        return root

题解 4 - python

• 编辑时间：2023-11-03
• 执行用时：40ms
• 内存消耗：15.66MB
• 编程语言：python
• 解法介绍：层序遍历中同时记录next。

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root: return root
        head = root
        p = head
        next_head = None
        while p:
            if p.left:
                if not next_head:
                    next_head = p.left
                    head = p.left
                else:
                    next_head.next = p.left
                    next_head = next_head.next
            if p.right:
                if not next_head:
                    next_head = p.right
                    head = p.right
                else:
                    next_head.next = p.right
                    next_head = next_head.next
            p = p.next
            if not p:
                p = head
                head = None
                next_head = None
        return root

题解 5 - cpp

• 编辑时间：2023-11-03
• 执行用时：8ms
• 内存消耗：16.93MB
• 编程语言：cpp
• 解法介绍：层序遍历中同时记录next。

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        Node *head = root, *p = head, *next_head = nullptr;
        while (p) {
            if (p->left) {
                if (!next_head) head = next_head = p->left;
                else next_head = next_head->next = p->left;
            }
            if (p->right) {
                if (!next_head) head = next_head = p->right;
                else next_head = next_head->next = p->right;
            }
            p = p->next;
            if (!p) p = head, head = next_head = nullptr;
        }
        return root;
    }
};