LeetCode 116. 填充每个节点的下一个右侧节点指针

Categories:

题目描述
思路分析
1. 解法一：层内指针遍历（推荐）
相似题目

题目描述

✅ 116. 填充每个节点的下一个右侧节点指针

思路分析

解法一：层内指针遍历（推荐）

核心思路：

该题是完美二叉树，可利用上一层已建立的 next 指针进行横向遍历。

对每一层，连接 left.next = right，再连接 right.next = cur.next.left。

逐层向下推进，不需要额外队列，空间 O(1)。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点个数。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }

        // leftMost 指向当前层最左节点
        Node leftMost = root;
        while (leftMost.left != null) {
            Node cur = leftMost;

            // 通过 next 指针遍历当前层
            while (cur != null) {
                cur.left.next = cur.right;
                if (cur.next != null) {
                    cur.right.next = cur.next.left;
                }
                cur = cur.next;
            }

            leftMost = leftMost.left;
        }

        return root;
    }
}

func connect(root *Node) *Node {
	if root == nil {
		return nil
	}

	// leftMost 指向当前层最左节点
	leftMost := root
	for leftMost.Left != nil {
		cur := leftMost

		// 通过 Next 指针遍历当前层
		for cur != nil {
			cur.Left.Next = cur.Right
			if cur.Next != nil {
				cur.Right.Next = cur.Next.Left
			}
			cur = cur.Next
		}

		leftMost = leftMost.Left
	}

	return root
}

相似题目

题目	难度	考察点
117. 填充每个节点的下一个右侧节点指针 II	中等	二叉树
102. 二叉树的层序遍历	中等	层序遍历
199. 二叉树的右视图	中等	层序遍历
513. 找树左下角的值	中等	层序遍历
637. 二叉树的层平均值	简单	层序遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/44904513