leetcode--589--N叉树的前序遍历

题目：
给定一个 N 叉树，返回其节点值的前序遍历。

例如，给定一个 3叉树 :

返回其前序遍历: [1,3,5,6,2,4]。

思路：
1、前序遍历：按照【根左右】的顺序遍历root节点

Python代码：

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution(object):

    def __init__(self):
        self.ret = []

    def preorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        ret = []
        if not root:
            return None
        self.ret.append(root.val)
        for item in root.children:
            self.preorder(item)
        return self.ret

C++代码：

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:

    vector<int> ret;

    vector<int> preorder(Node* root) {
        if (root==nullptr) {
            return ret;
        }
        ret.push_back(root->val);
        for (auto item : root->children){
            preorder(item);
        }
        
        return ret;
    }
};

思路2：
1、非递归版：定义一个队列，存放进去root。递归的pop出队列的首位元素，并按照从右往左的顺序依次将首位元素的子节点加入到队列中

Python代码：

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution(object):

    def __init__(self):
        self.ret = []

    def preorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        if not root:
            return None
        deque = [root]
        ret = []

        while deque:
            item = deque.pop()
            ret.append(item.val)
            for i in range(len(item.children)-1,-1,-1):
                deque.append(item.children[i])
        return ret