当前位置：首页 > news >正文

面试经典150题[074]：填充每个节点的下一个右侧节点指针 II（LeetCode 117）

news 2026/8/17 17:23:53

填充每个节点的下一个右侧节点指针 II（LeetCode 117）

题目链接：填充每个节点的下一个右侧节点指针 II（LeetCode 117）
难度：中等

1. 题目描述

给你一个二叉树的根节点root，请你将其中所有节点的next指针指向其右侧的节点。如果没有右侧节点，则next指针应设置为NULL。

初始时，所有next指针都设置为NULL。

树节点定义：

classNode: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

要求：

二叉树不一定是完美的（即不一定是满二叉树或完全二叉树）。
节点数 0 <= n <= 6000
-100 <= Node.val <= 100

示例：

输入: root = [1,2,3,4,5,null,7] 输出: [1,#,2,3,#,4,5,7,#] 解释: 给定二叉树如图所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

输入: root = [] 输出: []

2. 问题分析

2.1 规律

这是一个二叉树问题，需要将同一层的节点通过next指针连接起来，形成一个链表。
与 LeetCode 116 不同，本题的树不一定是完美的，因此不能假设每层都有完整的左右子节点。
核心问题：如何在不使用额外空间（如队列）的情况下，高效连接同一层节点？
类似于层序遍历，但需要处理缺失节点的情况。

2.2 贪心思路

我们使用常量空间的层级连接方法：

从根节点开始，逐层处理。
对于每一层，使用一个虚拟节点dummy来构建下一层的链表头，并用tail指针来连接下一层的子节点。
遍历当前层的节点（通过已连接的next指针），为每个节点的左右子节点建立连接：
- 如果有左子节点，连接到tail.next。
- 如果有右子节点，连接到tail.next。
当前层遍历结束后，将下一层的头节点设置为dummy.next，继续处理下一层。
这个方法利用了上一层的next指针来遍历当前层，避免使用队列，实现 O(1) 额外空间。
如果树为空或只有根节点，直接返回。

3. 代码实现

Python

classSolution:defconnect(self,root:'Node')->'Node':ifnotroot:returnroot head=rootwhilehead:dummy=Node(0)tail=dummy cur=headwhilecur:ifcur.left:tail.next=cur.left tail=tail.nextifcur.right:tail.next=cur.right tail=tail.nextcur=cur.nexthead=dummy.nextreturnroot

C++

classSolution{public:Node*connect(Node*root){if(!root)returnroot;Node*head=root;while(head){Node*dummy=newNode(0);Node*tail=dummy;Node*cur=head;while(cur){if(cur->left){tail->next=cur->left;tail=tail->next;}if(cur->right){tail->next=cur->right;tail=tail->next;}cur=cur->next;}head=dummy->next;// 注意：在C++中，需要手动删除dummy以避免内存泄漏，但LeetCode环境可忽略}returnroot;}};