LeetCode算法题-N-ary Tree Preorder Traversal(Java实现)
2024-09-27 16:14:52
这是悦乐书的第268次更新,第282篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第135题(顺位题号是589)。给定一个n-ary树,返回其节点值的前序遍历。例如,给定一个3-ary树:
1
/ | \
3 2 4
/ \
5 6
其前序遍历结果为:[1,3,5,6,2,4]。
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
利用递归。二叉树前序遍历是从根节点开始,然后是左子树,最后是右子树,题目给的是N-ary树,但是遍历节点的顺序还是和二叉树一样,从根节点开始,然后对其子节点(list数组)进行遍历,其子节点进行前序遍历,和题目性质一样,可以直接使用递归的方式参与计算。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {
if (root == null) {
return new ArrayList<Integer>();
}
List<Integer> list = new ArrayList<Integer>();
getValue(root, list);
return list;
}
public List<Integer> getValue(Node root, List<Integer> list) {
if (root == null) {
return null;
}
list.add(root.val);
if (root.children != null) {
for (Node n : root.children) {
getValue(n, list);
}
}
return list;
}
}
03 第二种解法
我们也可以使用迭代的方式来实现前序遍历。这里我们使用栈,借助其先进后出的特性,有一点需要注意的是,在处理其子节点时,我们需要从后往前入栈,这样出栈的时候就是从前往后了。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {
if (root == null) {
return new ArrayList<Integer>();
}
List<Integer> list = new ArrayList<Integer>();
Stack<Node> stack = new Stack<Node>();
stack.push(root);
while (!stack.isEmpty()) {
Node temp = stack.pop();
list.add(temp.val);
if (temp.children != null) {
for (int i=temp.children.size()-1; i >= 0; i--) {
stack.push(temp.children.get(i));
}
}
}
return list;
}
}
04 小结
算法专题目前已日更超过四个月,算法题文章135+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!
最新文章
- 微信小程序之基础简介
- SQL 语句调优 where 条件 数据类型 临时表 索引
- 深入研究虚拟机之垃圾收集(GC)算法实现
- MapReduce排序输出
- iframe自动适应高度1
- ExtJs store加载
- make file 详
- 关于js关闭浏览器技术细谈
- nginx反向代理node.js获取客户端IP
- Python+Visual Studio
- MySQL巧建sum索引帮我们提高至少100%的效率
- 洛谷P3474 KUP-Plot purchase
- 样条之埃尔米特(Hermite)
- 歌曲播放页面的数据vuex管理
- (01)JVM-内存三大核心区域以及分析
- hdu 1698 线段树 区间更新 区间求和
- DVWA平台v1.9-Command Injection
- Vim 新手节省时间的小技巧
- ubuntu boost.python
- SpringBoot(一)_Eclipse的安装和使用
热门文章
- BBS论坛(一)
- 死磕 java集合之ArrayList源码分析
- 【3分钟就会系列】使用Ocelot+Consul搭建微服务吧!
- 『宝藏 状态压缩DP NOIP2017』
- 从.Net到Java学习第二篇——IDEA and start spring boot
- .NetCore&;Linux&;Docker&;Portainer踩坑历险记
- C++STL模板库适配器之queue队列
- NET快速信息化系统开发框架 V3.2 ->;WinForm部分全部重构为Dev风格界面
- ES6躬行记(18)——迭代器
- kubernetes进阶之一:简单例子