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

589. N叉树的前序遍历迭代法：null指针与栈的巧妙配合

news 来源：原创 2025/6/18 3:32:14

一、题目描述

给定一个N叉树的根节点，返回其节点值的前序遍历结果。前序遍历的定义是：先访问根节点，再依次遍历每个子节点（从左到右）。例如，对于如下N叉树：

    1/ | \3  2  4
/ \
5  6

前序遍历结果为：[1,3,5,6,2,4]。

二、核心难点：null指针与迭代逻辑的设计

难点1：null指针的作用——标记节点处理阶段

在迭代法中，我们需要模拟递归的“回溯”过程。null指针在此充当阶段分隔符，用于区分以下两个阶段：

入栈子节点阶段：当遇到非null节点时，先将所有子节点逆序入栈，再将当前节点和null入栈，标记“子节点已入栈，等待处理当前节点值”。
收集节点值阶段：当遇到null时，说明其前一个节点的子节点已全部入栈，此时弹出该节点并收集值（类似递归中的“回溯时处理”）。

难点2：迭代逻辑的核心——栈的状态控制

子节点逆序入栈：由于栈是后进先出（LIFO），将子节点按逆序入栈（如[C,B,A]入栈，弹出顺序为A,B,C），确保前序遍历的顺序（根→A→B→C）。
双栈操作：通过“非null节点入栈子节点→入栈自身和null”的模式，确保在处理完所有子节点后，才会处理当前节点值，避免重复访问。

三、代码解析：迭代法的完整实现

import java.util.*;class Solution {public List<Integer> preorder(Node root) {List<Integer> res = new ArrayList<>();if (root == null) return res;Stack<Node> stack = new Stack<>();stack.push(root); // 根节点入栈while (!stack.isEmpty()) {Node node = stack.pop(); // 弹出节点if (node != null) {// 1. 逆序入栈所有子节点if (node.children != null) {for (int i = node.children.size() - 1; i >= 0; i--) {stack.push(node.children.get(i));}}// 2. 入栈当前节点和null（标记处理阶段）stack.push(node);stack.push(null);} else {// 遇到null，说明前一个节点的子节点已处理完毕，收集当前节点值Node valNode = stack.pop();res.add(valNode.val);}}return res;}
}

四、迭代流程模拟：以示例N叉树为例

初始状态

栈：[1]
结果：[]

第一次循环

弹出1（非null）：
- 子节点为[3,2,4]，逆序入栈为4,2,3。
- 入栈1和null，栈变为：[4,2,3,1,null]。

第二次循环

弹出null：
- 弹出1，加入结果[1]。
- 栈变为：[4,2,3]。

第三次循环

弹出3（非null）：
- 子节点为[5,6]，逆序入栈为6,5。
- 入栈3和null，栈变为：[4,2,6,5,3,null]。

第四次循环

弹出null：
- 弹出3，加入结果[1,3]。
- 栈变为：[4,2,6,5]。

第五次循环

弹出5（非null，无子节点）：
- 入栈5和null，栈变为：[4,2,6,5,null]。

第六次循环

弹出null：
- 弹出5，加入结果[1,3,5]。
- 栈变为：[4,2,6]。

后续循环

类似流程处理6、2、4，最终结果为[1,3,5,6,2,4]。

五、关键知识点：前序与后序迭代法的对比

前序遍历（当前代码）

核心逻辑：
非null节点→逆序入栈子节点→入栈自身和null
确保先处理子节点，再通过null触发收集当前节点值。

后序遍历（修改版代码）

public List<Integer> postorder(Node root) {List<Integer> res = new ArrayList<>();if (root == null) return res;Stack<Node> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {Node node = stack.pop();if (node != null) {stack.push(node); // 先入栈当前节点stack.push(null); // 标记后序处理// 正序入栈子节点（与前序相反）if (node.children != null) {for (Node child : node.children) {stack.push(child);}}} else {Node valNode = stack.pop();res.add(valNode.val); // 后序收集}}return res;
}

关键修改：
1. 子节点正序入栈（前序为逆序），确保后序遍历顺序（左→右→根）。
2. null标记后处理当前节点，确保子节点先被处理。

六、null指针的本质：模拟递归的压栈与回溯

递归流程	迭代（栈+null）模拟
调用preorder(root)	stack.push(root)
递归前序遍历子节点	逆序入栈子节点，压栈root和null
回溯时处理root.val	遇到null，弹出root并收集值

null指针的作用相当于递归中的“回溯点”，通过栈的状态机控制，将递归的隐式调用栈转化为显式的栈操作，实现非递归算法。

七、总结：迭代法的优势与适用场景

优势

空间可控：避免递归深度过大导致的栈溢出（如树高为1e5时）。
灵活性：可方便修改为后序、层序等其他遍历方式（只需调整入栈顺序和标记逻辑）。

适用场景

所有需要深度优先遍历（DFS）的树结构问题，尤其是N叉树（递归可能复杂）。
面试中要求“非递归”解法的场景。

核心思想

通过栈模拟递归的调用栈，利用null等标记符区分节点的“预处理阶段”和“回溯处理阶段”，实现对遍历顺序的精确控制。理解这一思想后，可举一反三解决二叉树、N叉树的各种遍历问题。

589. N叉树的前序遍历迭代法：null指针与栈的巧妙配合

一、题目描述给定一个N叉树的根节点，返回其节点值的前序遍历结果。前序遍历的定义是：先访问根节点，再依次遍历每个子节点（从左到右）。例如，对于如下N叉树： 1/ | \3 2 4 / \ 5 6前序遍历结果…...

编程日记 2025/5/29 19:50:11

【洗车店专用软件】佳易王洗车店多项目会员管理系统：一卡多用扣次软件系统实操教程 #扣次洗车管理软件

一、软件试用版资源文件下载说明 （一）若您想体验软件功能，可通过以下方式获取软件试用版资源文件： 访问头像主页：进入作者头像主页，找到第一篇文章，点击文章最后的卡片按钮，即可了解…...

编程日记 2025/5/29 9:48:36

小红书笔记详情接口如何调用？实操讲解。

调用小红书笔记详情接口通常需要经过申请权限、构建请求、发送请求并处理响应等步骤，以下是详细的实操讲解： 一、申请接口权限注册小红书开放平台账号访问小红书开放平台官网/第三方开放平台，按照提示完成注册流程，提供必要的…...

编程日记 2025/6/1 16:31:37

leetcode 57. Insert Interval

题目描述代码：由于intervals已经按照左端点排序，并且intervals中的区间全部不重叠，那么可以断定intervals中所有区间的右端点也已经是有序的。先二分查找intervals中第一个其右端点>newInterval左端点的区间。然后按照类似于56. Merge In…...

编程日记 2025/5/27 15:24:30

杰理ac696配置mic

省电容mic有概率不出声解决办法如下...

编程日记 2025/5/27 8:25:31

COMSOL随机参数化表面流体流动模拟

基于粗糙度表面的裂隙流研究对于理解地下水的流动、污染物传输以及与之相关的地质灾害（如滑坡）等方面具有重要意义。本研究通过蒙特卡洛方法生成随机表面形貌，并利用COMSOL Multiphysics对随机参数化表面的微尺度流体流动进行模拟。参数化…...

编程日记 2025/5/26 6:38:12

Linux远程连接服务

远程连接服务器简介远程连接服务器通过文字或图形接口方式来远程登录系统，让你在远程终端前登录linux主机以取得可操作主机接口（shell），而登录后的操作感觉就像是坐在系统前面一样。远程连接服务器的功能分享主机的运算能力远…...

编程日记 2025/5/29 13:53:20

用Python绘制梦幻星空

用Python绘制梦幻星空在这篇教程中，我们将学习如何使用Python创建一个美丽的星空场景。我们将使用Python的图形库Pygame和随机库来创建闪烁的星星、流星和月亮，打造一个动态的夜空效果。项目概述我们将实现以下功能： 创建深蓝色的夜…...

编程日记 2025/5/27 6:01:53

1、错误 Problem: problem with installed package selinux-policy-targeted-3.14.3-41.el8.noarch package fail2ban-server-1.0.2-3.el8.noarch requires (fail2ban-selinux if selinux-policy-targeted), but none of the providers can be installed - package fail2ban-…...

编程日记 2025/5/27 1:23:13

网安面试经（1）

1.说说IPsec VPN 答：IPsec VPN是利用IPsec协议构建的安全虚拟网络。它通过加密技术，在公共网络中创建加密隧道，确保数据传输的保密性、完整性和真实性。常用于企业分支互联和远程办公，能有效防范数据泄露与篡改，但部署…...

编程日记 2025/5/27 4:42:56

【每天一个知识点】意图传播（Intent Propagation）

在人工智能（AI）快速发展的背景下，自然语言处理（NLP）已成为推动智能系统理解与生成自然语言的核心技术。其中，“意图识别”作为人机交互的关键步骤，已被广泛应用于智能客服、对话系统、语音助手等场景。而“意图传播”（Intent Propagation）作为更深层的机制，逐渐成为当…...

编程日记 2025/5/26 21:51:02

【串流VR手势】Pico 4 Ultra Enterprise 在 SteamVR 企业串流中无法识别手势的问题排查与解决过程（Pico4UE串流手势问题）

写在前面的话此前（用Pico 4U）接入了MRTK3，现项目落地需要部署，发现串流场景中，Pico4UE的企业串流无法正常识别手势。（一体机方式部署使用无问题） 花了半小时解决，怕忘，…...

编程日记 2025/5/29 16:53:40

工具：shell命令提示符自定义之显示GIT当前分支

1 背景在命令行操作，每次想查看当前分支都要手动执行命令（git branch）太麻烦了，想着在命令提示符上面显示当前分支，很直观也很方便 2 实现编辑 vim ~/.bashrc 文件，添加如下内容 function update_prom…...

编程日记 2025/5/27 7:44:31

现代计算机图形学Games101入门笔记(十四)

Irradiance 微小的能量/微小的面积用Irradiance解释能量大小解释冬夏 Intensity没变，但是Irradiance是衰减的，外圈面积变大，单位面积上接受的能量就变小了。入射进来离开这里就是从某个方向来了一个能量，经过反射&#xff0c…...

编程日记 2025/5/29 9:39:56

前端开发笔记与实践

一、Vue 开发规范与响应式机制 1. 组件命名规范自定义组件使用大驼峰命名法（如 MyComponent），符合 Vue 官方推荐，便于与原生 HTML 元素区分。 2. Proxy vs defineProperty 特性Proxy（Vue3）Object.defi…...

编程日记 2025/5/26 5:57:27

机器学习知识自然语言处理入门

一、引言：当文字遇上数学 —— 自然语言的数字化革命在自然语言处理（NLP）的世界里，计算机要理解人类语言，首先需要将文字转化为数学向量。早期的 One-Hot 编码如同给每个词语分配一个唯一的 “房间号”，例…...

编程日记 2025/5/27 7:10:02

泰迪杯特等奖案例深度解析：基于多级二值化与CNN回归的车牌识别系统设计

（第八届泰迪杯数据挖掘挑战赛特等奖案例全流程拆解）一、案例背景与核心挑战 1.1 行业痛点与场景需求在智慧交通与无感支付场景中，车牌识别是核心环节。传统车牌识别系统在复杂光照、污损车牌、多角度倾斜等场景下存在显著缺陷。根据某智慧油站2024年运营数据显示，高峰期…...

编程日记 2025/5/17 9:50:42

ai agent(智能体)开发 python高级应用5：crawl4ai 如何建立一个全面的知识库第一步找分类

让我们充分利用爬虫功能建立自己丰富的知识库， 第一步找分类以下是一个层次分明、覆盖全面的知识库分类体系，分为9大主类、43个子类，并融入交叉学科和新兴领域设计： 一、经济与商业宏观经济（全球经济/国家政策&a…...

编程日记 2025/5/28 16:31:48

Solon Ai Flow 编排开发框架发布预告（效果预览）

Solon Ai 在推出 Solon Ai Mcp 后，又将推出 Solon Ai Flow。 1、Solon Ai Flow 是个啥？ Solon Ai Flow 是一个智能体编排开发框架。它是框架！不是工具，不是产品（这与市面上流行的工具和产品，有较大差别&a…...

编程日记 2025/5/26 8:01:08

【言语】刷题5（填空）

front：刷题5 第一个词排除人迹罕至人迹罕至：很少有人去的地方。指偏僻荒涼的地方。（荒郊野岭既视感的一个词） 第二个空锁定B，太贴合语义了第三个空排除一文不值，百无一用，现在这题已经可以过了…...

编程日记 2025/5/29 10:53:33

技术解码 | 腾讯云SRT弱网优化

随着互联网基础设施和硬件设备的不断发展。广大直播观众对于直播观看的清晰度，延时等方面的体验要求越来越高，直播也随之进入了低延迟高码率的时代，直播传输技术也面临着越来越高的要求和挑战。腾讯视频云为此在全链路上针对流媒体传输不断深…...

编程日记 2025/5/28 11:07:12

“分布形态“

一、分布形态的基础分类 1、正态分布（对称分布）（1）特征：钟型曲线，均值=中位数=众数；约68%数据在μσ范围内，95%在μ2σ内。（2）应用：身高、体重、测量误差等自然现象。（3）重要性：多数统计方法（如T检验、方差分析）假设数据正态性。 2、偏态分布（1）左偏（负…...

编程日记 2025/6/3 15:30:56

Android minSdk从21升级24后SO库异常

问题 minSdk从21调整到24后： java.nio.file.NoSuchFileException: /data/app/~~Z9s2NfuDdclOUwUBLKnk0A/com.rs.unity- Bg31QvFwF4qsCwv2XCqT-w/split_config.arm64_v8a.apkjava.nio.file.NoSuchFileException: /data/app/~~Z9s2NfuDdclOUwUBLKnk0A/com.rs.unity-…...

编程日记 2025/5/29 13:25:35

C#进阶（2）stack（栈）

前言我们前面介绍了ArrayList，今天就介绍另一种数据结构——栈。这是栈的基本形式，博主简单画了一下，你看个意思就行，很明显，这种数据有一种特征：先进后出。因为先进来的数据会在下面，下面是密闭的，所以只能取后面进来的。 C#为我们封好了这种数据结构，我们不用担…...

编程日记 2025/5/26 6:00:00

Linux du 命令终极指南：从基础到精通

文章目录 Linux du 命令终极指南：从基础到精通du 命令简介常用参数详解常见用法示例查看当前目录总大小查看当前目录及其子目录占用空间只显示当前目录总占用空间查看目录下每个文件和子目录的大小查看某目录深度为 1 的大小分布查看某目录并排除日志文件查看多个目…...

编程日记 2025/5/28 15:28:04

【Linux网络】数据链路层

数据链路层用于两个设备（同一种数据链路节点）之间进行传递。认识以太网 “以太网” 不是一种具体的网络，而是一种技术标准；既包含了数据链路层的内容，也包含了一些物理层的内容。例如：规定了网络拓扑结…...

编程日记 2025/6/4 8:06:14

水库雨水情测报与安全监测系统解决方案

一、方案概述本水库雨水情测报与安全监测解决方案的核心目标在于利用尖端的技术手段，确保对水库雨水情势以及大坝安全状况的持续监控和及时预警，从而为水库的稳定运行提供坚实的支持和保障。该方案严格遵循“统筹协调、因库制宜、实用有效、信息共享”的…...

编程日记 2025/5/28 7:46:40

Shotcut：免费开源的视频编辑利器

Shotcut是一款功能强大且完全免费的开源视频编辑软件，专为需要高效、灵活视频编辑的用户设计。它支持多种常见视频格式，如MP4、AVI、MOV等，并提供了丰富的视频编辑功能，满足用户在不同场景下的需求。无论是初学者还是专业人士&…...

编程日记 2025/5/29 16:38:54

学习海康VisionMaster之直方图工具

一：进一步学习了今天学习下VisionMaster中的直方图工具：就是统计在ROI范围内进行灰度级分布的统计二：开始学习 1：什么是直方图工具？ 直方图工具针对输入灰度图像的指定ROI区域，输出该区域的图像灰度直方…...

编程日记 2025/5/26 22:18:56

AI 笔记 -基于retinaface的FPN上采样替换为CARAFE

上采样替换为CARAFE 引言内容感知特征重组（CARAFE）公式化核预测模块引言简介：CARAFE（Content-Aware ReAssembly of FEatures），是用于增强卷积神经网络特征图的上采样方法，论文被 ICCV 2019 接…...

编程日记 2025/5/29 10:09:59

Visual Studio 2022 中添加“高级保存选项”及解决编码问题

文章目录一、背景二、方法方法一：通过菜单栏手动添加（推荐）方法二：通过拖拽快速添加（替代方案） 三、验证与使用四、补充说明五、所能解决的问题一、背景 VS 在开发cmake项目的过程中，可能会遇…...

编程日记 2025/5/29 11:48:12

SQLMesh 增量模型从入门到精通：5步实现高效数据处理

本文深入解析 SQLMesh 中的增量时间范围模型，介绍其核心原理、配置方法及高级特性。通过实际案例说明如何利用该模型提升数据加载效率，降低计算资源消耗，并提供配置示例与最佳实践建议，帮助读者在实际项目中有效应用这一强大功能。…...

编程日记 2025/5/27 7:46:01

嵌入式开发书籍推荐

嵌入式开发是将计算机技术、微电子技术与各行业应用相结合的综合技术，学习过程中需要多方面知识储备。以下精选书籍，从基础到进阶，助你系统掌握嵌入式开发知识。基础理论类《计算机组成原理》（唐朔飞版）&#xff1…...

编程日记 2025/5/29 17:02:09

实变函数第二章点集

2 点集 2.1 欧式空间 2.1.1 度量空间、欧式空间 Definition \textbf{Definition} Definition 度量空间 (距离空间) 若 ∀ x , y ∈ X : ∃ d : ( x , y ) → R \forall x,y\in X:\exists d:(x,y)\to\mathbb{R} ∀x,y∈X:∃d:(x,y)→R，满足： d ( x , y…...

编程日记 2025/5/27 6:07:34

国芯思辰| 轮速传感器AH741对标TLE7471应用于汽车车轮速度感应

在汽车应用中，轮速传感器可用于车轮速度感应，为 ABS、ESC 等安全系统提供精确的轮速信息，帮助这些系统更好地发挥作用，在紧急制动或车辆出现不稳定状态时，及时调整车轮的制动力或动力分配。国芯思辰两线制差分式轮速…...

编程日记 2025/5/28 7:26:45

MySQL中innodb的ACID

一、什么ACID A：原子性，事务是一个不可分割的工作单位，事务中的操作要么全部成功，要么全部失败回滚；C：一致性，事务必须保证数据库从一个一致性的状态变换成另一个一致性的状态，如A给…...

编程日记 2025/6/4 2:03:09

基于对抗性后训练的快速文本到音频生成：stable-audio-open-small 模型论文速读

Fast Text-to-Audio Generation with Adversarial Post-Training 论文解析一、引言与背景文本到音频系统的局限性：当前文本到音频生成系统性能虽佳，但推理速度慢（需数秒至数分钟），限制了其在创意领域的应用。研究…...

编程日记 2025/6/1 12:37:57

java 使用zxing生成条形码（可自定义文字位置、边框样式）

最新工作中遇到生成条形码的需求，经过一番摸索之后找到了zxing这个工具类，实现效果如下： 首先引入依赖： <dependency><groupId>com.google.zxing</groupId><artifactId&g…...

编程日记 2025/5/29 12:48:34

4.3/Q1，Charls最新文章解读

文章题目：Longitudinal trajectories of disability index and associated factors in Chinese older adults DOI：10.1016/j.jnha.2025.100530 中文标题：中国老年人残疾指数纵向轨迹及相关因素发表杂志：J Nutr Health Aging 影响…...

编程日记 2025/5/28 8:38:45

CSS- 2.1 实战之图文混排、表格、表单、学校官网一级导航栏

本系列可作为前端学习系列的笔记，代码的运行环境是在HBuilder中，小编会将代码复制下来，大家复制下来就可以练习了，方便大家学习。 HTML系列文章已经收录在前端专栏，有需要的宝宝们可以点击前端专栏查看！ 系…...

编程日记 2025/5/29 10:53:32

Android studio 实现弹出表单编辑界面

方法 1：使用 AlertDialog（简单表单） 适用于简单的表单场景。 1. 创建表单布局（XML） 在 res/layout 中新建 dialog_form.xml： <?xml version"1.0" encoding"utf-8"?> <L…...

编程日记 2025/6/1 9:29:08

涂色不踩雷：如何优雅解决 LeetCode 栅栏涂色问题

文章目录摘要描述例子： 题解答案（Swift）题解代码分析动态规划核心思路初始条件示例测试及结果示例 1：示例 2：示例 3： 时间复杂度空间复杂度总结实际场景联系摘要在用户体验和界面设计中，颜…...

编程日记 2025/5/29 12:06:27

WL-G4048 Multi-Port PCIe 4.0 Switch

系列文章目录文章目录系列文章目录《WL-G4048 Multi-Port PCIe 4.0 Switch数据手册》总结一、芯片介绍二、芯片规格介绍（一）功能指标（二）管理调试和监控（三）参考时钟（四）系统复位 …...

编程日记 2025/6/2 3:47:24

基于Huber函数和最大相关熵的抗差滤波算法

最大熵滤波（Maximum Entropy Filtering）常用于信号处理中的谱估计和噪声抑制，尤其适用于短数据序列的高分辨率谱分析。一、最大熵滤波算法原理核心思想：在满足已知自相关函数约束的条件下，使信号的熵最大化。数学形…...

编程日记 2025/5/28 7:53:22

力扣-39.组合总和

题目描述给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合 ，并以列表形式返回。你可以按任意顺序返回这些组合。 candidates 中的同一个数字可以无限制重复被…...

编程日记 2025/5/27 7:45:21

医学图像分析中的大规模基准测试与增强迁移学习|文献速递-深度学习医疗AI最新文献

Title 题目 Large-scale benchmarking and boosting transfer learning for medical imageanalysis 医学图像分析中的大规模基准测试与增强迁移学习 01 文献速递介绍将在大规模摄影数据集（如ImageNet）上预训练的模型微调至医学图像领域&#xff08…...

编程日记 2025/5/29 20:00:55

深入浅出横向联邦学习、纵向联邦学习、联邦迁移学习

深入浅出解析横向联邦学习（Horizontal Federated Learning）、纵向联邦学习（Vertical Federated Learning）和联邦迁移学习（Federated Transfer Learning） 有多个机构（比如几家不同的银行&#x…...

编程日记 2025/5/29 12:46:14

vue复杂数据类型多层嵌套的监听

vue复杂数据类型多层嵌套的监听本来看前辈的做法是watch的嵌套，遇到这种复杂的数据结构还是不多，分享一下前辈的做法 let stopChildWatchList [] // 用于存放每个子监听器watch(() > data,(val) > {// 清除旧监听stopChildWatchList.forEach(…...

编程日记 2025/5/27 7:50:31

windows系统中下载好node无法使用npm

原因是 Windows PowerShell禁用导致的npm无法正常使用解决方法管理员打开Windows PowerShell 输入Set-ExecutionPolicy -Scope CurrentUser RemoteSigned 按Y 确认就解决了...

编程日记 2025/5/29 15:58:33

使用 Docker 部署 React + Nginx 应用教程

目录 1. 创建react项目结构2. 创建 .dockerignore3. 创建 Dockerfile4. 创建 nginx.conf5. 构建和运行6. 常用命令 1. 创建react项目结构 2. 创建 .dockerignore # 依赖目录 node_modules npm-debug.log# 构建输出 dist build# 开发环境文件 .git .gitignore .env .env.local …...

编程日记 2025/5/29 12:49:44