脚本宝典收集整理的这篇文章主要介绍了589. 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
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 叉树的前序遍历全部内容,希望文章能够帮你解决589. N 叉树的前序遍历所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。