589. N 叉树的前序遍历
2022/3/25 6:24:28
本文主要是介绍589. N 叉树的前序遍历,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
589. N 叉树的前序遍历
给定一个 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, 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 preorderHelper(Node *root, vector<int> &vec) { 24 if (root == nullptr) { 25 return; 26 } 27 vec.push_back(root->val); 28 int size = root->children.size(); 29 for (int i = 0; i < size; i++) { 30 preorderHelper(root->children[i], vec); 31 } 32 return; 33 } 34 vector<int> preorder(Node* root) { 35 vector<int> ans; 36 if (root == nullptr) { 37 return ans; 38 } 39 preorderHelper(root, ans); 40 return ans; 41 } 42 };
迭代解法:
1 class Solution { 2 public: 3 vector<int> preorder(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 ans.push_back(p->val); 14 int size = p->children.size(); 15 for (int i = size - 1; i >= 0; i--) { 16 s.push(p->children[i]); 17 } 18 } 19 return ans; 20 } 21 };
这篇关于589. N 叉树的前序遍历的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)