首页 / PYTHON / [LeetCode&Python] Problem 590. N-ary Tree Postorder Traversal

[LeetCode&Python] Problem 590. N-ary Tree Postorder Traversal

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode&Python] Problem 590. N-ary Tree Postorder Traversal，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1432字，纯文字阅读大概需要3分钟。

内容图文

Given an n-ary tree, return the postorder traversal of its nodes‘ values.

 

For example, given a 3-ary tree:

技术分享图片

 

Return its postorder traversal as: [5,6,3,2,4,1].

 

Note: Recursive solution is trivial, could you do it iteratively?

 

Recursion Solution:

"""
# 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]
        """
        def dfs(r):
            if not r:
                return
            else:
                for c in r.children:
                    dfs(c)
                result.append(r.val)
        
        result=[]
        dfs(root)
        return result

Iteration Solution:

"""
# 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 []
        
        # We can use a deque to store the solution
        res=collections.deque()
        # We use stack to store all the node
        #Every time, we only need to pick the top node in the stack
        #and store its value in res
        #And then we store its children in the stack. The right-most
        #child is stored in the top.
        #If our stack is empty, we finish our job.
        stack=[root]
        
        while stack:
            u=stack.pop()
            res.appendleft(u.val)
            for c in u.children:
                stack.append(c)
                
        #change deque back to list
        return list(res)

原文：https://www.cnblogs.com/chiyeung/p/9728816.html

内容总结

以上是互联网集市为您收集整理的[LeetCode&Python] Problem 590. N-ary Tree Postorder Traversal全部内容，希望文章能够帮你解决[LeetCode&Python] Problem 590. N-ary Tree Postorder Traversal所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1215982.html

来源：【匿名】