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

Categories:

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

题目描述

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

思路分析

解法一：层序遍历指针连接（推荐）

核心思路：

使用当前层的 next 指针遍历节点，不额外使用队列。

通过虚拟头结点 dummy 和尾指针 tail 将下一层节点串起来。

每处理完一层后，跳到 dummy.next 作为下一层起点。

复杂度分析：

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

空间复杂度：O(1)，不计递归栈和输出结构。

class Solution {
    public Node connect(Node root) {
        Node cur = root;

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

            for (Node node = cur; node != null; node = node.next) {
                if (node.left != null) {
                    // 连接下一层的左子节点
                    tail.next = node.left;
                    tail = tail.next;
                }
                if (node.right != null) {
                    // 连接下一层的右子节点
                    tail.next = node.right;
                    tail = tail.next;
                }
            }

            cur = dummy.next;
        }

        return root;
    }
}

func connect(root *Node) *Node {
    cur := root

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

        for node := cur; node != nil; node = node.Next {
            if node.Left != nil {
                // 连接下一层的左子节点
                tail.Next = node.Left
                tail = tail.Next
            }
            if node.Right != nil {
                // 连接下一层的右子节点
                tail.Next = node.Right
                tail = tail.Next
            }
        }

        cur = dummy.Next
    }

    return root
}

相似题目

题目	难度	考察点
116. 填充每个节点的下一个右侧节点指针	中等	层序遍历
102. 二叉树的层序遍历	中等	层序遍历
103. 二叉树的锯齿形层序遍历	中等	层序遍历
199. 二叉树的右视图	中等	层序遍历
117. 填充每个节点的下一个右侧节点指针 II	中等	层序遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/44642653