590. N 叉树的后序遍历
2022/3/25 6:24:07
本文主要是介绍590. N 叉树的后序遍历,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
590. N 叉树的后序遍历
给定一个 n 叉树的根节点root
,返回 其节点值的 后序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null
分隔(请参见示例)。
示例 1:
输入:root = [1,null,3,2,4,null,5,6] 输出:[5,6,3,2,4,1]
示例 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] 输出:[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
提示:
- 节点总数在范围
[0, 104]
内 0 <= Node.val <= 104
- n 叉树的高度小于或等于
1000
递归解法:
1 /* 2 // Definition for a Node. 3 class Node { 4 public: 5 int val; 6 vector<Node*> children; 7 8 Node() {} 9 10 Node(int _val) { 11 val = _val; 12 } 13 14 Node(int _val, vector<Node*> _children) { 15 val = _val; 16 children = _children; 17 } 18 }; 19 */ 20 21 class Solution { 22 public: 23 void postorderHelper(Node *root, vector<int> &vec) { 24 if (root == nullptr) { 25 return; 26 } 27 int size = root->children.size(); 28 for (int i = 0; i < size; i++) { 29 postorderHelper(root->children[i], vec); 30 } 31 vec.push_back(root->val); 32 return; 33 } 34 vector<int> postorder(Node* root) { 35 vector<int> ans; 36 if (root == nullptr) { 37 return ans; 38 } 39 postorderHelper(root, ans); 40 return ans; 41 } 42 };
迭代解法:
1 class Solution { 2 public: 3 vector<int> postorder(Node* root) { 4 vector<int> ans; 5 if (root == nullptr) { 6 return ans; 7 } 8 stack<Node*> s; 9 s.push(root); 10 while (!s.empty()) { 11 Node * p = s.top(); 12 s.pop(); 13 if (p != nullptr) { 14 s.push(p); 15 s.push(nullptr); 16 int size = p->children.size(); 17 for (int i = size - 1; i >= 0; i--) { 18 s.push(p->children[i]); 19 } 20 } else { 21 p = s.top(); 22 s.pop(); 23 ans.push_back(p->val); 24 } 25 } 26 return ans; 27 } 28 };
这篇关于590. N 叉树的后序遍历的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)