LeetCode C++ 589. N-ary Tree Preorder Traversal【Tree/DFS】简单
发布日期:2021-07-01 02:53:01
浏览次数:4
分类:技术文章
本文共 1930 字,大约阅读时间需要 6 分钟。
Given an n-ary tree, return the preorder traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Follow up:
Recursive solution is trivial, could you do it iteratively?
Example 1:
Input: root = [1,null,3,2,4,null,5,6]Output: [1,3,5,6,2,4]
Example 2:
Input: 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]Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]
Constraints:
- The height of the n-ary tree is less than or equal to
1000
- The total number of nodes is between
[0, 10^4]
题意:对N叉树进行先序遍历。
思路1 递归遍历
class Solution { public: vector ans; vector preorder(Node* root) { traversal(root); return ans; } void traversal(Node* root) { if (root) { ans.push_back(root->val); for (int i = 0; i < root->children.size(); ++i) preorder(root->children[i]); } }};
效率如下:
执行用时:44 ms, 在所有 C++ 提交中击败了75.59% 的用户内存消耗:104.3 MB, 在所有 C++ 提交中击败了22.77% 的用户
思路2 非递归遍历
如果使用教科书版本的非递归先序遍历,很难想到解题思路。但是如果使用简单版本,就很容易解决这道题:
- 二叉树的非递归先序遍历中,每次将当前结点的右孩子节点和左孩子节点依次压入栈中,注意是先右后左。然后将出栈节点输出,并且在将其右子节点和左子节点压入栈中。
- 推广到N叉树,就是将当前结点的孩子节点由右到左依次压入栈中。然后将出栈节点输出,并且将其孩子节点依次压入栈中。
时间和空间复杂度都是 O ( n ) O(n) O(n) 。代码如下:
class Solution { public: vector preorder(Node* root) { if (root == nullptr) return { }; vector ans; stackst; st.push(root); while (!st.empty()) { Node *temp = st.top(); st.pop(); ans.push_back(temp->val); //使用右值引用,注意:it是一个左值 for (auto &&it = temp->children.rbegin(); it != temp->children.rend(); ++it) st.push(*it); } return ans; } };
效率如下,没有函数调用的栈空间消耗:
执行用时:44 ms, 在所有 C++ 提交中击败了75.59% 的用户内存消耗:11.4 MB, 在所有 C++ 提交中击败了58.87% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108933853 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月08日 08时53分18秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
如何证明Java子类实际上是拥有父类的私有属性
2019-05-02
关于Maven-3.3.3版本的问题
2019-05-02
Java编程思想笔记——第二章 一切都是对象
2019-05-02
Java编程思想笔记——第三章 操作符
2019-05-02
Java编程思想笔记——第四章 控制执行流程
2019-05-02
Java编程思想笔记——第五章 初始化和清理
2019-05-02
Java编程思想笔记——第八章 多态
2019-05-02
关于java.text.SimpleDateFormat的parse()方法存在的坑
2019-05-02
Java编程思想笔记——第十章 内部类
2019-05-02
Java编程思想笔记——第十四章 类型信息
2019-05-02
在阿里的ECS上安装ElasticSearch
2019-05-02
为什么商业搜索引擎选择的索引更新策略是完全重建策略
2019-05-02
MySQL学习笔记——慢查询
2019-05-02
elastic-job监控平台搭建
2019-05-02
HttpClient教程(4.5.2)——前言
2019-05-02
RedHat离线安装htop源码包
2019-05-02
Java线程与线程状态
2019-05-02
SpringBoot学习心得
2019-05-02
Java枚举使用技巧
2019-05-02
Drools入门——HelloWorld
2019-05-02