Leetcode 589. N-ary Tree Preorder Traversal

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

• Recursive

/* // Definition for a Node. class Node { public:int val;vector<Node*> children;Node() {}Node(int _val, vector<Node*> _children) {val = _val;children = _children;} }; */
class Solution {
public:vector<int> preorder(Node* root) {vector<int> result;if(!root) {return result;}preOrderTraverse(result, root);return result;}void preOrderTraverse(vector<int>& result, Node* root) {if(!root) {return;}result.push_back(root->val);int size = root->children.size();for(int i = 0; i < size; i++) {preOrderTraverse(result, root->children[i]);}}
};

• Iterative

/* // Definition for a Node. class Node { public:int val;vector<Node*> children;Node() {}Node(int _val, vector<Node*> _children) {val = _val;children = _children;} }; */
class Solution {
public:vector<int> preorder(Node* root) {vector<int> result;if(!root) {return result;}preOrderTraverse(result, root);return result;}void preOrderTraverse(vector<int>& result, Node* root) {stack<Node*> list;list.push(root);while(!list.empty()) {Node* current = list.top();list.pop();result.push_back(current->val);int size = current->children.size();for(int i = size - 1; i >= 0; i--) {list.push(current->children[i]);}}}
};

Reference

1. https://leetcode.com/problems/n-ary-tree-preorder-traversal/description/