Leetcode0590: N 叉树的后序遍历(simple, 递归，迭代)_离散数学多叉树的后序遍历

目录

1. 题目描述

2. 解题分析

2.1 递归

2.2 迭代

3. 代码实现

---

1. 题目描述

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

n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[5,6,3,2,4,1]

 

示例 2：
输入：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]
输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]

 

提示：
节点总数在范围 [0, 10^4] 内
0 <= Node.val <= 10^4
n 叉树的高度小于或等于 1000

进阶：递归法很简单，你可以使用迭代法完成此题吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题分析

2.1 递归

        N叉树的后序遍历与二叉树的后序遍历基本相同。

        是先遍历所有子树，最后遍历节点自身。参考Leetcode0145: 二叉树的后序遍历。

        代码参见：postorderRecursion()

2.2 迭代

        与二叉树遍历一样，也可以用迭代的方式来实现。

        但是由于N叉树的N是不确定的（二叉树确定性地最多只有左子树和右子树），所以一方面需要使用for-loop循环处理来遍历children；另一方面，由于是for-loop内嵌于while循环之中，break/continue的控制需要注意，与二叉树时有差异。处理流程如下：

        (1)栈、visited、ans初始化

        (2)将根节点入栈，同时将根节点加入visited

        (3)当栈不为空：

                (3-1)从栈中弹出一个节点

                (3-2)遍历该节点的子节点，对于每个不在visited中的子节点：

                        如果该子节点为叶子节点，将其值加入ans以及visited，回到(3-2)

                        如果该子节点不是叶子节点，将该节点和该子节点入栈，回到(3)                

                (3-4)如果该节点还有子节点待处理（即尚未加入ans）回到(3)

                (3-5)将其值加入ans，将其加入visited，回到(3)

        以以上示例1为例，围绕进出栈的处理步骤如下所示：

        (1) 1入

        (2) 1出

        (3) 1入，3入

        (4) 3出，进ans/visited

        (5) 3入，5入

        (6) 5出，进ans/visited

        (7) 3出

        (8) 3入，6入

        (9) 6出，进ans/visited

        (10) 3出，进ans/visited

        (11) 1出

        (12) 1入，2入

        (13) 2出，进ans/visited

        (14) 1出

        (15) 1入，4入

        (16) 4出，进ans/visited

        (17) 1出，进ans/visited

        虽然略显繁琐，但是手动推演一遍，是确保完全理解的必经之路。

3. 代码实现

import time
from typing import List	
from collections import deque
 
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
class Solution:
    # def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    def postorderTraversalRecursion(self, root: TreeNode) -> List[int]:
        if root==None:
            return []
        
        ans = []
        if root.left != None:
            left_lst = self.postorderTraversal(root.left)
            ans = ans + left_lst
        if root.right != None:
            right_lst = self.postorderTraversal(root.right)
            ans = ans + right_lst
        ans.append(root.val)
        
        return ans        
 
    def postorderTraversalIteration(self, root: TreeNode) -> List[int]:
        if root==None:
            return []
        ans = []        
        s = deque()  # Used as stack, instead of FIFO
        visited = set()
        s.append(root)
        while len(s)>0:
            hasChildrenNotYetProcessed = False
            node = s.pop()
            for child in node.children:   
                if (child not in visited):
                    s.append(node)
                    s.append(child)
                    hasChildrenNotYetProcessed = True
                    break
            if hasChildrenNotYetProcessed:
                continue
            ans.append(node.val)
            visited.add(node)                
        return ans            

回到主目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。)https://chenxiaoyuan.blog.csdn.net/article/details/123040889