LeetCode | 0590. N叉树的后序遍历【Python】

亦凉 2023-01-11 03:47 117阅读 0赞

## Problem ##

[LeetCode][]

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

*Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).*

**Follow up:**

Recursive solution is trivial, could you do it iteratively?

**Example 1:**

![img][]

Input: root = [1,null,3,2,4,null,5,6]
    Output: [5,6,3,2,4,1]

**Example 2:**

![img][img 1]

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
    Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

**Constraints:**

*  The height of the n-ary tree is less than or equal to `1000`
 *  The total number of nodes is between `[0, 10^4]`

## 问题 ##

[力扣][Link 1]

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

例如，给定一个 3叉树 :

![img][]

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

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

## 思路 ##

**DFS**

### Python3 代码 ###

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

**BFS**

遍历子树的时候加入顺序是类似根右左，因此最后要做一下逆序。

### Python3 代码 ###

""" # 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]:
            # BFS
            if not root:
                return []
    
            q = [root]
            res = []
            while q:
                # 弹出列表尾部的一个元素
                node = q.pop()
                res.append(node.val)
                # 顺序加入
                for child in node.children:
                    q.append(child)
            return res[::-1]

## GitHub 链接 ##

[Python][]

[LeetCode]: https://leetcode.com/problems/n-ary-tree-postorder-traversal/
[img]: /images/20221119/a7ebdd17c73b418aa1e710176929945d.png
[img 1]: /images/20221119/6cb9eaf166ca434a9de98fc84cadd031.png
[Link 1]: https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/
[Python]: https://github.com/Wonz5130/LeetCode-Solutions/blob/master/solutions/0590-N-ary-Tree-Postorder-Traversal/0590.py