递归和迭代【Py/Java/C++三种语言详解】LeetCode每日一题240218【树DFS】LeetCode 589、 N 叉树的前序遍历

有LeetCode算法/华为OD考试扣扣交流群可加 948025485
可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1336了解算法冲刺训练

文章目录

  • 题目描述
  • 解题思路
  • 代码
    • 方法一:递归法
      • Python
      • Java
      • C++
      • 时空复杂度
    • 方法二:迭代法
      • Python
      • Java
      • C++
      • 时空复杂度
  • 华为OD算法/大厂面试高频题算法练习冲刺训练

题目描述

给定一个 n 叉树的根节点 root ,返回 其节点值的 前序遍历

n 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。

示例 1

输入:root = [1,null,3,2,4,null,5,6]
输出:[1,3,5,6,2,4]

示例 2

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出:[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

提示

  • 节点总数在范围 [0, 10(4)]
  • 0 <= Node.val <= 10(4)
  • n 叉树的高度小于或等于 1000

进阶:递归法很简单,你可以使用迭代法完成此题吗?

解题思路

本题的递归解法无非是将LeetCode144、二叉树的前序遍历 中的

ans.append(node.val)
self.dfs(ans, node.left)
self.dfs(ans, node.right)

改为

self.ans.append(root.val)
for children in root.children:if children:self.dfs(children)

即可。即始终维持先访问根节点的值,再递归遍历所有子节点这样的顺序。

迭代法类似二叉树的BFS,只不过是把维护一个队列改为维护一个栈。其核心过程为

stack = [root]
while(len(stack)):node = stack.pop()ans.append(node.val)for children in node.children[::-1]:if children:stack.append(children)
return ans

注意每一个子节点入栈的顺序是逆序的,即for children in node.children[::-1]

这是由栈后进先出的特定来决定的,对于每一个node而言,node的第一个子节点最后入栈,第一个出栈,这样才能确保是结果是子节点从左到右的前序遍历

另外,由于是前序遍历,访问父节点的始终位于遍历子节点的前面

代码

方法一:递归法

Python

class Solution:# 1.递归法def dfs(self, root: 'Node'):# 先父节点,后子节点self.ans.append(root.val)for children in root.children:if children:self.dfs(children)def preorder(self, root: 'Node') -> List[int]:if not root:return [] self.ans = list()self.dfs(root)return self.ans

Java

class Solution {// 递归法private List<Integer> ans = new ArrayList<>();private void dfs(Node root) {if (root == null) return;// 先父节点,后子节点ans.add(root.val);for (Node child : root.children) {if (child != null) {dfs(child);}}}public List<Integer> preorder(Node root) {if (root == null) return new ArrayList<>();ans.clear();dfs(root);return ans;}
}

C++

class Solution {
public:// 递归法vector<int> ans;void dfs(Node* root) {if (!root) return;// 先父节点,后子节点ans.push_back(root->val);for (Node* child : root->children) {if (child) {dfs(child);}}}vector<int> preorder(Node* root) {if (!root) return {};ans.clear();dfs(root);return ans;}
};

时空复杂度

时间复杂度:O(N)。仅需一次遍历整棵树。

空间复杂度:O(``1``)。忽略递归所调用的编译栈。

方法二:迭代法

Python

class Solution:def preorder(self, root: 'Node') -> List[int]:ans = list()if not root:return []stack = [root]  # 用栈维护DFS过程while(len(stack)):node = stack.pop()ans.append(node.val)for children in node.children[::-1]:if children:stack.append(children)return ans

Java

class Solution {// Iterative Solutionpublic List<Integer> preorder(Node root) {List<Integer> ans = new ArrayList<>();if (root == null)return ans;Stack<Node> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {Node node = stack.pop();ans.add(node.val);for (int i = node.children.size() - 1; i >= 0; i--) {if (node.children.get(i) != null) {stack.push(node.children.get(i));}}}return ans;}
}

C++

class Solution {
public:vector<int> preorder(Node* root) {vector<int> ans;if (!root)return ans;stack<Node*> stack;stack.push(root);while (!stack.empty()) {Node* node = stack.top();stack.pop();ans.push_back(node->val);for (int i = node->children.size() - 1; i >= 0; i--) {if (node->children[i] != NULL) {stack.push(node->children[i]);}}}return ans;}
};

时空复杂度

时间复杂度:O(N)。仅需一次遍历整棵树。

空间复杂度:O(N)。栈所占最大空间。


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务300+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2812862.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

北邮毕业论文Latex模板使用教程(Windows)

1latex模板下载 下载地址&#xff1a; https://github.com/rioxwang/BUPTGraduateThesis2安装编译环境 TEX Live 2014 或者CTEX 2.9.2.164&#xff0c;以及更高的版本. 下载其中一个即可 &#xff08;1&#xff09;TEX Live下载地址&#xff1a; https://tug.org/texlive/acq…

JAVA学习笔记12

1.键盘输入语句 1.1 介绍 ​ *在编程中&#xff0c;需要接收用户输入的数据&#xff0c;就可以使用键盘输入语句来获取。 1.2 步骤 ​ 1.导入该类的所在包&#xff0c;java.util.* ​ 2.创建该类对象&#xff08;声明变量&#xff09; ​ 3.调用里面的功能 import java.…

Aigtek前置微小信号放大器在传感器检测中的应用有哪些

传感器是将物理量转换为电信号的装置&#xff0c;其精度和灵敏度直接影响到检测系统的性能。而传感器的输出信号通常都非常微弱&#xff0c;需要进行放大处理才能得到可靠的测量结果。前置微小信号放大器&#xff0c;作为一种重要的传感器检测元件&#xff0c;在传感器检测中发…

游戏服务器租用价格大比拼,腾讯云阿里云京东云疯狂比价!

游戏服务器租用多少钱一年&#xff1f;1个月游戏服务器费用多少&#xff1f;阿里云游戏服务器26元1个月、腾讯云游戏服务器32元&#xff0c;华为云26元&#xff0c;游戏服务器配置从4核16G、4核32G、8核32G、16核64G等配置可选&#xff0c;游戏专业服务器公网带宽10M、12M、15M…

CentOS7 Hive2.3.8安装

CentOS7 Hive2.3.8 安装 建议从头用我的博客&#xff0c;如果用外教的文件到 一、9)步骤了&#xff0c;就用他的弄完&#xff0c;数据库不一样&#xff0c;在9步骤前还能继续看我的 一、 安装MySQL 0.0&#xff09;查询mariadb,有就去0.1&#xff09;&#xff0c;没有就不管…

x-cmd pkg | g - 功能和交互更为丰富的 `ls` 替代方案

目录 简介首次用户功能特点竞品和相关作品进一步阅读 简介 g 是一项用 Go 开发的、功能和交互更为丰富的 ls 替代方案。它拥有 100 多个功能选项&#xff0c;主要是通过各式图标、各种布局选项和 git status 集成来增强视觉效果&#xff0c;并且支持多种输出格式&#xff0c;如…

Administrative-divisions-of-China:中华人民共和国行政区划数据

Administrative-divisions-of-China是中华人民共和国行政区划&#xff1a;省级&#xff08;省份&#xff09;、 地级&#xff08;城市&#xff09;、 县级&#xff08;区县&#xff09;、 乡级&#xff08;乡镇街道&#xff09;、 村级&#xff08;村委会居委会&#xff09; &a…

c++史上最全算法详解,0基础可秒懂!(爆肝4万字)

本文极长&#xff0c;建议点赞收藏后看&#xff01; 质量分95&#xff01;&#xff01; 文章目录 -1.C 标准0.语法基础1. C头文件2. C命名空间3. 主函数4. 变量类型5. ASCII码6. 注释 1.顺序结构一、代码示例二、例题1&#xff1a;求圆的面积三、例题2&#xff1a;求解一元二次…

常见集合框架底层原理

常见集合框架底层原理 常见的集合有哪些 Java集合类主要由两个接口Collection和Map派生出来的&#xff0c;Collection有三个子接口: List、 Set、Queue List代表了有序可重复集合&#xff0c;可直接根据元素的索引来访问Set代表了无序集合&#xff0c;只能根据元素本身来访问…

【Leetcode每日一题】二分查找 - 有效的完全平方数(难度⭐)(19)

1. 题目解析 Leetcode链接&#xff1a;367. 有效的完全平方数 这个问题的理解其实相当简单&#xff0c;只需看一下示例&#xff0c;基本就能明白其含义了。 核心在于判断给定的整数是否可以开方成两个整数相乘&#xff0c;可以就返回false&#xff0c;反之返回true。 2. 算法…

【c语言】基础数据类型

文章目录 1、什么数据类型2、常量3、变量4、整型数据5、浮点型数据6、字符型数据7、字符串数据 1、什么数据类型 ​ 在生活中&#xff0c;裁缝做衣服需要用到不同的化纤、棉花、丝绸等布料&#xff0c;炒不同的菜需要油、盐等不同的配方&#xff0c;而程序员在编写程序时也需要…

4核8G服务器多少钱?腾讯云和阿里云哪家便宜?

4核8G云服务器多少钱一年&#xff1f;阿里云ECS服务器u1价格955.58元一年&#xff0c;腾讯云轻量4核8G12M带宽价格是646元15个月&#xff0c;阿腾云atengyun.com整理4核8G云服务器价格表&#xff0c;包括一年费用和1个月收费明细&#xff1a; 云服务器4核8G配置收费价格 阿里…

Vue.js+SpringBoot开发快递管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、研究内容2.1 数据中心模块2.2 快递类型模块2.3 快递区域模块2.4 快递货架模块2.5 快递档案模块 三、界面展示3.1 登录注册3.2 快递类型3.3 快递区域3.4 快递货架3.5 快递档案3.6 系统基础模块 四、免责说明 一、摘要 1.1 项目介绍 …

Vue源码系列讲解——生命周期篇【七】(模板编译阶段)

目录 1. 前言 2. 模板编译阶段分析 2.1 两种$mount方法对比 2.2 完整版的vm.$mount方法分析 3. 总结 1. 前言 前几篇文章中我们介绍了生命周期的初始化阶段&#xff0c;我们知道&#xff0c;在初始化阶段各项工作做完之后调用了vm.$mount方法&#xff0c;该方法的调用标志…

前后端分离PHP+vue+mysql城市轨道交通线路公交查询系统

医院、厕所、药店、派出所、学校、营业厅、快递、银行 开发语言&#xff1a;php 后端框架&#xff1a;Thinkphp 前端框架&#xff1a;vue.js 服务器&#xff1a;apache 数据库&#xff1a;mysql 运行环境:phpstudy/wamp/xammp等 A.美食 快餐、中餐、自助餐、火锅、烧烤、奶…

STM32 I2C学习

IIC总线协议介绍 IIC&#xff1a;Inter Integrated Circuit&#xff0c;集成电路总线&#xff0c;是一种同步、串行、半双工通信总线。 同步&#xff1a;需要时钟线 串行&#xff1a;数据一位一位地发送 半双工&#xff1a;同一时间只能接受或发送&#xff0c;不能同时发送或…

【Unity】如何从现有项目中抽取好用的资源

【背景】 在做Unity项目的过程中引入各种各样的Package&#xff0c;有的Package很大&#xff0c;但是觉得非常有用的可能只是几个Prefab或者Material等。如果直接拷贝想要的Prefab和Material&#xff0c;又需要自己确认所有有依赖关系的资源。 如果能将所有日常经受项目中自己…

SQLlabs46关

看看源码 最终我们的id是放到order by后面了 如果我们直接用列去排序 ?sortusername/password username&#xff1a; passward 可以看到顺序是不同的&#xff0c;当然第一列第二列第三列也可以&#xff0c;基本上都是这个原理&#xff0c;那怎么去实现注入呢&#xff0c;我…

杰理701N可视化SDK之组合键代码设计

杰理701N可视化SDK组合键代码设计 组合键相关代码修改组合键消息处理代码SDK加入组合键代码引出的问题 杰理701N可视化SDK目前只支持在可视化工具中配置按键和按键功能, 还不支持在可视化工具中直接加入组合键的功能. 需要在SDK中做些修改才可以实现组合键的功能. 本篇文章演示…

文本生成图像新SOTA!RealCompo:逼真和构图的动态平衡(清北最新)

文章链接&#xff1a;https://arxiv.org/pdf/2402.12908 最近AI生成内容领域取得了令人激动的很多成果&#xff0c;比如Sora、StableDiffusion-3等等。今天给大家分享另一个内容生成领域的SOTA模型——RealCompo&#xff0c;这是一种新的文本到图像生成框架&#xff0c;旨在利…