小黑leetcode之旅:590. N 叉树的后序遍历

1.非递归法

""" # 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 not root:
            return []
        stack = [root]
        display = []

        while stack:
            top = stack[-1]
            
            if not top.children or top.children[0].val in display:
                display.append(top.val)
                stack.pop()
            else:
                stack.extend(reversed(top.children))
            
        return display

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]:
        display = []
        if not root:
            return []
        
        def after_node(node):

            for child in node.children:
                after_node(child)

            display.append(node.val)
        after_node(root)
        return display

3.先根遍历逆转法

""" # 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]:
        display = []
        if not root:
            return display
        stack = [root]
        while stack:
            top = stack.pop()
            display.append(top.val)

            stack.extend(top.children)
        return reversed(display)