【leetcode刷题】T152-N叉树的后序遍历

木又AI帮

发布于 2019-08-29 17:30:26

39600

代码可运行

文章被收录于专栏：木又AI帮木又AI帮

运行总次数：0

代码可运行

木又连续日更第12天（12/138）

木又的第152篇leetcode解题报告

二叉树类型第42篇解题报告

leetcode第590题：N叉树的后序遍历

https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/

【题目】

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

例如，给定一个 3叉树 :

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

说明: 递归法很简单，你可以使用迭代法完成此题吗?

【思路】

参考二叉树的后序遍历：首先从左往右递归访问孩子节点，然后访问根节点。

【代码】

python版本

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""
class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        if not root:
            return []
        res = []
        self.helper(root, res)
        return res

    def helper(self, node, res):
        for child in node.children:
            self.helper(child, res)
        res.append(node.val)

C++版本

/*
// 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> postorder(Node* root) {
        vector<int> res;
        if(!root)
            return res;
        helper(root, res);
        return res;
    }

    void helper(Node* node, vector<int>& res){
        for(auto child: node->children)
            helper(child, res);
        res.push_back(node->val);
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-08-27，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树