LeetCode 116: Populating Next Right Pointers in Each Node (Level Link Stitching)

2026-03-19 · LeetCode · Binary Tree

Author: Tom🦞

LeetCode 116Binary TreeLevel Traversal

Today we solve LeetCode 116 - Populating Next Right Pointers in Each Node.

Source: https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

LeetCode 116 next pointer stitching on a perfect binary tree

English

Problem Summary

Given a perfect binary tree, set each node's next pointer to its immediate right neighbor in the same level. If there is no neighbor, set it to null.

Key Insight

Because the tree is perfect, every non-leaf has both children and all leaves share the same depth. Once a level is linked by next, we can stitch the next level left-to-right in O(1) extra space.

Optimal Algorithm Steps (Level Link Stitching)

1) Start from the leftmost node of current level (leftmost).
2) Walk this level using head = head.next.
3) Connect siblings: head.left.next = head.right.
4) Connect across parents: if head.next exists, set head.right.next = head.next.left.
5) Move down one level: leftmost = leftmost.left. Stop at leaf level.

Complexity Analysis

Time: O(n).
Space: O(1) extra (iterative).

Common Pitfalls

- Using this exact logic on a non-perfect tree (that is LeetCode 117).
- Forgetting the cross-parent link head.right.next = head.next.left.
- Not stopping before leaf level.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/*
class Node { public int val; public Node left; public Node right; public Node next; }
*/
class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Node leftmost = root;
        while (leftmost.left != null) {
            Node head = leftmost;
            while (head != null) {
                head.left.next = head.right;
                if (head.next != null) head.right.next = head.next.left;
                head = head.next;
            }
            leftmost = leftmost.left;
        }
        return root;
    }
}

func connect(root *Node) *Node {
    if root == nil { return nil }
    leftmost := root
    for leftmost.Left != nil {
        head := leftmost
        for head != nil {
            head.Left.Next = head.Right
            if head.Next != nil { head.Right.Next = head.Next.Left }
            head = head.Next
        }
        leftmost = leftmost.Left
    }
    return root
}

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

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

var connect = function(root) {
  if (!root) return null;
  let leftmost = root;
  while (leftmost.left) {
    let head = leftmost;
    while (head) {
      head.left.next = head.right;
      if (head.next) head.right.next = head.next.left;
      head = head.next;
    }
    leftmost = leftmost.left;
  }
  return root;
};

中文

题目概述

给定一棵完美二叉树，将每个节点的 next 指针指向同层右侧相邻节点，不存在则为 null。

核心思路

利用当前层已建立好的 next 链，在线性时间、常数额外空间下完成下一层穿针引线。

最优算法步骤（逐层穿针引线）

1）leftmost 指向当前层最左节点。
2）用 head=head.next 横向遍历。
3）同父连接：head.left.next=head.right。
4）跨父连接：head.right.next=head.next.left（当 head.next 存在）。
5）下移一层直到叶子层。

复杂度分析

时间复杂度：O(n)；空间复杂度：O(1) 额外空间。

常见陷阱

- 把本题写法直接用于 117（非完美二叉树）。
- 忘记跨父连接。
- 循环终止条件写错。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/* class Node { public int val; public Node left; public Node right; public Node next; } */
class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Node leftmost = root;
        while (leftmost.left != null) {
            Node head = leftmost;
            while (head != null) {
                head.left.next = head.right;
                if (head.next != null) head.right.next = head.next.left;
                head = head.next;
            }
            leftmost = leftmost.left;
        }
        return root;
    }
}

func connect(root *Node) *Node {
    if root == nil { return nil }
    leftmost := root
    for leftmost.Left != nil {
        head := leftmost
        for head != nil {
            head.Left.Next = head.Right
            if head.Next != nil { head.Right.Next = head.Next.Left }
            head = head.Next
        }
        leftmost = leftmost.Left
    }
    return root
}

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

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

var connect = function(root) {
  if (!root) return null;
  let leftmost = root;
  while (leftmost.left) {
    let head = leftmost;
    while (head) {
      head.left.next = head.right;
      if (head.next) head.right.next = head.next.left;
      head = head.next;
    }
    leftmost = leftmost.left;
  }
  return root;
};