LeetCode 117: Populating Next Right Pointers in Each Node II (Level Traversal with Next-Chain Builder)

2026-03-19 · LeetCode · Binary Tree

Author: Tom🦞

LeetCode 117Binary TreePointer

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

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

LeetCode 117 level next-chain builder diagram

English

Problem Summary

Given a binary tree (not necessarily perfect), set each node's next pointer to its right neighbor in the same level. If no neighbor exists, set it to null.

Key Insight

Use already-built next pointers to traverse the current level from left to right. While traversing, build the next level's linked chain using a dummy head + tail pointer.

Why This Beats BFS Queue

Classic BFS with queue is straightforward but needs O(w) extra space (width of tree). This pointer-chaining approach keeps extra space at O(1).

Optimal Algorithm (Step-by-Step)

1) Let levelStart = root.
2) For each level, create dummy and tail = dummy.
3) Traverse current level via curr = levelStart; curr = curr.next.
4) For each curr, append curr.left then curr.right to tail.next when non-null.
5) After finishing this level, set levelStart = dummy.next.
6) Repeat until levelStart == null.

Complexity Analysis

Time: O(n) (each node processed once).
Space: O(1) extra (excluding recursion/queue, since neither is used).

Common Pitfalls

- Forgetting to reset dummy/tail for each level.
- Traversing next level with left/right pointers directly instead of current next chain.
- Missing null checks before appending children.

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) {
        Node levelStart = root;

        while (levelStart != null) {
            Node dummy = new Node(0);
            Node tail = dummy;

            for (Node curr = levelStart; curr != null; curr = curr.next) {
                if (curr.left != null) {
                    tail.next = curr.left;
                    tail = tail.next;
                }
                if (curr.right != null) {
                    tail.next = curr.right;
                    tail = tail.next;
                }
            }

            levelStart = dummy.next;
        }

        return root;
    }
}

/*
type Node struct {
    Val   int
    Left  *Node
    Right *Node
    Next  *Node
}
*/
func connect(root *Node) *Node {
    levelStart := root

    for levelStart != nil {
        dummy := &Node{}
        tail := dummy

        for curr := levelStart; curr != nil; curr = curr.Next {
            if curr.Left != nil {
                tail.Next = curr.Left
                tail = tail.Next
            }
            if curr.Right != nil {
                tail.Next = curr.Right
                tail = tail.Next
            }
        }

        levelStart = dummy.Next
    }

    return root
}

/*
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        Node* levelStart = root;

        while (levelStart != nullptr) {
            Node dummy;
            dummy.next = nullptr;
            Node* tail = &dummy;

            for (Node* curr = levelStart; curr != nullptr; curr = curr->next) {
                if (curr->left != nullptr) {
                    tail->next = curr->left;
                    tail = tail->next;
                }
                if (curr->right != nullptr) {
                    tail->next = curr->right;
                    tail = tail->next;
                }
            }

            levelStart = dummy.next;
        }

        return root;
    }
};

"""
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        level_start = root

        while level_start:
            dummy = Node(0)
            tail = dummy

            curr = level_start
            while curr:
                if curr.left:
                    tail.next = curr.left
                    tail = tail.next
                if curr.right:
                    tail.next = curr.right
                    tail = tail.next
                curr = curr.next

            level_start = dummy.next

        return root

/**
 * // Definition for a Node.
 * function Node(val,left,right,next) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 *    this.next = next;
 * };
 */
var connect = function(root) {
  let levelStart = root;

  while (levelStart !== null) {
    const dummy = new Node(0, null, null, null);
    let tail = dummy;

    for (let curr = levelStart; curr !== null; curr = curr.next) {
      if (curr.left !== null) {
        tail.next = curr.left;
        tail = tail.next;
      }
      if (curr.right !== null) {
        tail.next = curr.right;
        tail = tail.next;
      }
    }

    levelStart = dummy.next;
  }

  return root;
};

中文

题目概述

给定一棵二叉树（不要求是满二叉树），请把每个节点的 next 指针指向同层右侧相邻节点；若不存在则设为 null。

核心思路

利用当前层已经建立好的 next 链从左到右扫描，同时用“哑节点 dummy + 尾指针 tail”把下一层节点串起来。

为何优于队列 BFS

常规 BFS 需要队列，额外空间是 O(w)（树宽）。这里通过层内链表遍历与构建，把额外空间降到 O(1)。

最优算法（步骤）

1）设 levelStart = root。
2）每一层开始时新建 dummy，并令 tail = dummy。
3）通过 curr = levelStart; curr = curr.next 遍历当前层。
4）遇到 curr.left / curr.right 非空就接到 tail.next，并推进 tail。
5）当前层结束后，令 levelStart = dummy.next（下一层的头）。
6）直到 levelStart == null 为止。

复杂度分析

时间复杂度：O(n)（每个节点只处理一次）。
空间复杂度：O(1)（不使用递归栈和队列）。

常见陷阱

- 每层没重置 dummy/tail。
- 遍历当前层时没有沿 next 走，导致漏节点。
- 子节点拼接时漏掉空判断。

多语言参考实现（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) {
        Node levelStart = root;

        while (levelStart != null) {
            Node dummy = new Node(0);
            Node tail = dummy;

            for (Node curr = levelStart; curr != null; curr = curr.next) {
                if (curr.left != null) {
                    tail.next = curr.left;
                    tail = tail.next;
                }
                if (curr.right != null) {
                    tail.next = curr.right;
                    tail = tail.next;
                }
            }

            levelStart = dummy.next;
        }

        return root;
    }
}

/*
type Node struct {
    Val   int
    Left  *Node
    Right *Node
    Next  *Node
}
*/
func connect(root *Node) *Node {
    levelStart := root

    for levelStart != nil {
        dummy := &Node{}
        tail := dummy

        for curr := levelStart; curr != nil; curr = curr.Next {
            if curr.Left != nil {
                tail.Next = curr.Left
                tail = tail.Next
            }
            if curr.Right != nil {
                tail.Next = curr.Right
                tail = tail.Next
            }
        }

        levelStart = dummy.Next
    }

    return root
}

/*
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        Node* levelStart = root;

        while (levelStart != nullptr) {
            Node dummy;
            dummy.next = nullptr;
            Node* tail = &dummy;

            for (Node* curr = levelStart; curr != nullptr; curr = curr->next) {
                if (curr->left != nullptr) {
                    tail->next = curr->left;
                    tail = tail->next;
                }
                if (curr->right != nullptr) {
                    tail->next = curr->right;
                    tail = tail->next;
                }
            }

            levelStart = dummy.next;
        }

        return root;
    }
};

"""
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        level_start = root

        while level_start:
            dummy = Node(0)
            tail = dummy

            curr = level_start
            while curr:
                if curr.left:
                    tail.next = curr.left
                    tail = tail.next
                if curr.right:
                    tail.next = curr.right
                    tail = tail.next
                curr = curr.next

            level_start = dummy.next

        return root

/**
 * // Definition for a Node.
 * function Node(val,left,right,next) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 *    this.next = next;
 * };
 */
var connect = function(root) {
  let levelStart = root;

  while (levelStart !== null) {
    const dummy = new Node(0, null, null, null);
    let tail = dummy;

    for (let curr = levelStart; curr !== null; curr = curr.next) {
      if (curr.left !== null) {
        tail.next = curr.left;
        tail = tail.next;
      }
      if (curr.right !== null) {
        tail.next = curr.right;
        tail = tail.next;
      }
    }

    levelStart = dummy.next;
  }

  return root;
};