[ LeetCode 590 ] N 叉樹的後序周遊

原文連結：https://www.keketec.club/posts/11228680/

每天分享一個LeetCode題目

每天 5 分鐘，一起進步

LeetCode N 叉樹的後序周遊，位址: https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/

樹結點類

class TreeNode(object):
    def __init__(self, val, children=[]):
        self.val = val
        self.children = children
           

N 叉樹的後序周遊

利用遞歸，依然遵循「左右根」的周遊原則

def postorder(self, root):
    if not root:
        return
    for node in root.children:
        self.postorder(node)
    print(root.val, end=" ")
           

是不是看起來特别簡單，但是這樣不符合 LeetCode 題目中的要求

需要将結果放到一個數組中，是以需要提前初始化一個 list 進行存放

def postorder_lc(self, root):
    res = []

    def post_order(root):
        if not root:
            return
        for node in root.children:
            post_order(node)
        res.append(root.val)

    post_order(root)
    return res
           

完整代碼

# -*- coding:utf-8 -*-
# !/usr/bin/env python

# 樹結點類
class Node(object):
    def __init__(self, val=None, children=[]):
        self.val = val
        self.children = children


class Solution(object):
    def postorder(self, root):
        if not root:
            return
        for node in root.children:
            self.postorder(node)
        print(root.val, end=" ")

    def postorder_lc(self, root):
        res = []

        def post_order(root):
            if not root:
                return
            for node in root.children:
                post_order(node)
            res.append(root.val)

        post_order(root)
        return res


if __name__ == "__main__":
    # 建立節點
    root = Node('A')
    node_B = Node('B')
    node_C = Node('C')
    node_D = Node('D')
    node_E = Node('E')
    node_F = Node('F')
    node_G = Node('G')
    node_H = Node('H')
    node_I = Node('I')
    # 建構三叉樹
    #        A
    #      / | \
    #     B  C  D
    #    /|\   / \
    #   E F G H   I
    root.children = [node_B, node_C, node_D]
    node_B.children = [node_E, node_F, node_G]
    node_D.children = [node_H, node_I]

    s = Solution()
    s.postorder(root)
    print("\n")
    print(s.postorder_lc(root))