LeetCode C++ 589. N-ary Tree Preorder Traversal【Tree/DFS】简单
发布日期:2021-07-01 02:53:01
浏览次数:3
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月30日 00时28分35秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
人际吸引法则
2019-05-02
常见的心理学效应
2019-05-02
克伦巴赫alpha系数
2019-05-02
《少有人走的路》读书笔记
2019-05-02
《秘密全在小动作上》读书笔记
2019-05-02
性心理发展阶段
2019-05-02
memwatch 内存检测工具
2019-05-02
利用doxygen生成python文档
2019-05-02
git checkout -b
2019-05-02
[cherry-pick, merge, rebase]
2019-05-02
git reflog
2019-05-02
git reset hard/soft/mixed区别
2019-05-02
git fetch, rebase,pull,merge 区别
2019-05-02
有效英语商务写作
2019-05-02
思维导图操作书 读书笔记
2019-05-02
工作压力与情绪管理
2019-05-02
工作压力与情绪管理读书笔记二
2019-05-02
linux 特殊权限的介绍
2019-05-02
LINUX各个发行版本之间的区别
2019-05-02
YUM config/make install 与apt-gethi中间的区别
2019-05-02