LeetCode 题目 116:填充每个节点的下一个右侧节点指针

2024-05-12 09:04

本文主要是介绍LeetCode 题目 116:填充每个节点的下一个右侧节点指针,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

作者介绍:10年大厂数据\经营分析经验,现任字节跳动数据部门负责人。
会一些的技术:数据分析、算法、SQL、大数据相关、python,欢迎探讨交流
欢迎加入社区:码上找工作
作者专栏每日更新:
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化:企业实战案例
漫画版算法详解
python源码解读
程序员必备的数学知识与应用

题目描述

给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树的定义如下:

class Node:def __init__(self, val=0, left=None, right=None, next=None):self.val = valself.left = leftself.right = rightself.next = next

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 None

初始状态下,所有 next 指针都被设置为 None

方法一:层序遍历(BFS)

解题步骤:
  1. 使用队列进行层序遍历。
  2. 对于每一层的节点,通过队列的长度来确定节点的数量。
  3. 遍历当前层的节点,将每个节点的 next 指向队列中的下一个节点。
  4. 最后一个节点的 next 指向 None
Python 代码示例
from collections import dequedef connect(root):"""使用层序遍历来填充每个节点的下一个右侧节点指针。参数:root (Node): 完美二叉树的根节点。返回:Node: 修改后的树的根节点。"""# 如果根节点为空,则直接返回Noneif not root:return None# 初始化队列,并将根节点加入队列queue = deque([root])# 当队列不为空时,进行层序遍历while queue:# 获取当前层的节点数量size = len(queue)# 遍历当前层的每个节点for i in range(size):# 从队列中取出一个节点node = queue.popleft()# 如果不是当前层的最后一个节点,将当前节点的next指向队列中的下一个节点if i < size - 1:node.next = queue[0]# 如果当前节点有左子节点,将左子节点加入队列if node.left:queue.append(node.left)# 如果当前节点有右子节点,将右子节点加入队列if node.right:queue.append(node.right)# 返回根节点return root

方法一利用层序遍历(BFS)来填充每个节点的下一个右侧节点指针,下面通过 ASCII 图形来说明这个方法的工作过程。

考虑一个完美二叉树如下所示:

        1/ \2   3/ \ / \4  5 6  7
算法图解

我们使用队列来按层级遍历这棵树,并设置每个节点的 next 指针。以下是各个步骤的图解说明:

初始状态
  1. 初始化队列以包含根节点。
队列: [1]
第一层处理
  1. 取出节点 1,发现它有左右子节点 2 和 3,将这两个节点加入队列。
队列: [2, 3]
next指针连接: 1 -> None
  1. 设置节点 1 的 next 指向 None(因为它是第一层的唯一节点)。
第二层处理
  1. 取出节点 2,由于它不是队列中的最后一个节点,设置 next 指向队列中的下一个节点(节点 3)。同时将节点 2 的子节点 4 和 5 加入队列。
队列: [3, 4, 5]
next指针连接: 2 -> 3
  1. 取出节点 3,设置 next 指向 None(因为它是当前层的最后一个节点),将节点 3 的子节点 6 和 7 加入队列。
队列: [4, 5, 6, 7]
next指针连接: 3 -> None
第三层处理
  1. 处理节点 4, 5, 6, 7 类似,按顺序设置 next 指针:
队列: [5, 6, 7]
next指针连接: 4 -> 5
队列: [6, 7]
next指针连接: 5 -> 6
队列: [7]
next指针连接: 6 -> 7
队列: []
next指针连接: 7 -> None

在每一步中,我们从队列中移除一个节点,如果该节点不是当前层的最后一个节点,则将其 next 指针设置指向队列中的下一个节点。这样,每一层的节点都通过 next 指针连成一条链。当处理完当前层的所有节点后,队列中就包含了下一层的所有节点,重复以上步骤直到队列为空。这样的遍历确保了每个节点的 next 指针正确地指向了其右侧的节点。

方法二:使用已建立的 next 指针

解题步骤:
  1. 从根节点开始,利用上一层的 next 指针来遍历和链接当前层的节点。
  2. 对于每个节点,链接其左子节点到右子节点,右子节点到下一个节点的左子节点(如果存在)。
Python 代码示例
def connect(root):"""利用已建立的 next 指针来填充每个节点的下一个右侧节点指针。参数:root (Node): 完美二叉树的根节点。返回:Node: 修改后的树的根节点。"""# 如果根节点为空,则直接返回Noneif not root:return None# 初始化leftmost指针,这个指针始终指向每一层的最左侧节点leftmost = root# 当左侧节点存在时,继续处理下一层while leftmost.left:# 使用head指针遍历当前层的节点,head初始指向当前层的最左侧节点head = leftmostwhile head:# 将当前节点的左子节点的next指向右子节点head.left.next = head.right# 如果当前节点的next不为空,将右子节点的next指向当前节点next的左子节点if head.next:head.right.next = head.next.left# 移动到当前层的下一个节点head = head.next# 移动到下一层的最左侧节点leftmost = leftmost.left# 返回根节点return root

方法三:递归法

解题步骤:
  1. 递归地连接每个节点的左子节点到其右子节点。
  2. 连接相邻子树的右子节点到左子节点。
Python 代码示例
def connect(root):if not root or not root.left:return rootroot.left.next = root.rightif root.next:root.right.next = root.next.leftconnect(root.left)connect(root.right)return root

方法四:使用额外的节点追踪下一层的开始

解题步骤:
  1. 使用一个额外的节点 dummy 来追踪每一层的开始。
  2. 通过一个循环连接同一层的所有节点。
Python 代码示例
def connect(root):if not root:return Nonecurrent = rootwhile current:dummy = Node(0)tail = dummywhile current:if current.left:tail.next = current.lefttail = tail.nextif current.right:tail.next = current.righttail = tail.nextcurrent = current.nextcurrent = dummy.nextreturn root

方法五:迭代优化

解题步骤:
  1. 类似于方法二,但使用迭代而非递归。
  2. 遍历每一层,连接相应的节点。
Python 代码示例
def connect(root):if not root:return Nonenode = rootwhile node and node.left:next_level = node.leftwhile node:node.left.next = node.rightnode.right.next =node.next.left if node.next else Nonenode = node.nextnode = next_levelreturn root

算法分析

  • 时间复杂度:所有方法都需要遍历每个节点,因此时间复杂度为 O(N),其中 N 是树中的节点数。
  • 空间复杂度
    • 方法一:O(N),需要额外的队列。
    • 方法二至五:O(1),只使用常数额外空间。

不同算法的优劣势对比

  • 层序遍历(方法一)直观且易于理解,但需要额外的空间来存储队列。
  • 使用已建立的 next 指针(方法二)是空间复杂度最优的解法,适合空间敏感的应用。
  • 递归法(方法三)代码简洁,但在非尾递归的编译器上可能导致栈溢出。
  • 使用额外节点(方法四)适合不熟悉指针操作的场景。
  • 迭代优化(方法五)提供了一个折中的解决方案,空间复杂度低,且较易于理解。

应用示例

这些方法可以用在需要层级遍历但希望节约空间的场景,如实时数据处理、游戏编程中的场景管理,或任何需要快速访问同一层级节点的数据结构设计中。

这篇关于LeetCode 题目 116:填充每个节点的下一个右侧节点指针的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/982189

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return