多味的LeetCode --- 590.N叉树的后序遍历-蒲公英云

多味的LeetCode --- 590.N叉树的后序遍历

题目描述：

给定一个 N 叉树，返回其节点值的后序遍历。例如，给定一个 3叉树 :

在这里插入图片描述
返回其后序遍历: [5,6,3,2,4,1]。

解题思路1: 迭代法

由于后续遍历的顺序是：左—右—根。因此，需要按照先子树后根节点的顺序进行遍历。

参考博客：快乐的LeetCode之遍历二叉树之前序、中序、后序、层序

代码1： 递归法

Python版：

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
class Solution:
    def __init__(self):
        self.ret = []
    def postorder(self, root: 'Node') -> List[int]:
        if not root:
            return None
        for child in root.children:
            self.postorder(child)
        self.ret.append(root.val)
        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> postorder(Node* root) {
        if (root == nullptr){
            return ret;
        }
        for (auto child:root -> children){
            postorder(child);
        }
        ret.push_back(root->val);
        return ret;
    }
};

解题思路2: 迭代法

代码2：

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if root is None:
            return []
        stack, output = [root,],[]
        output = []
        while stack:
            node = stack.pop()
            if root is not None:
                output.append(node.val)
            for child in node.children:
                stack.append(child)
        return output[::-1]