### 题目描述 给定一个 n 叉树的根节点 root ，返回 其节点值的** 后序遍历** 。 n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。 ### 输入输出 #### 示例1  ``` 输入：root = [1,null,3,2,4,null,5,6] 输出：[5,6,3,2,4,1] ``` ### 题目解答 #### 思路1 采用递归的方式，遇到一个节点，如果有孩子节点就访问孩子，直到没有孩子节点时访问自己并返回， **算法复杂度：** 时间复杂度：对于n个节点时间复杂度为O(N) 空间复杂度：可能需要深度为n的栈，遍历的时候将所有节点入栈处理，所需空间O(N) #### 思路2 采用非递归的方式，利用栈模拟，首先将root作为栈顶元素将其入栈。首先取栈顶部的元素。如果该元素没有孩子，或者之前已经访问过，这是第二次访问。那么将该节点加入结果列表中，并且出栈。如果该元素有孩子的话，那么将其入栈，并且将节点加入visit数组中，下次弹栈的时候就知道出栈已经访问过了，进行后序遍历即可。 **算法复杂度：** 同上方法、 时间复杂度：对于n个节点时间复杂度为O(N) 空间复杂度：可能需要深度为n的栈，遍历的时候将所有节点入栈处理，所需空间O(N) #### 代码实现 ```python ## 递归的解法 class Solution: def __init__(self): self.res = list() def postorder(self, root: 'Node') -> List[int]: def order(root): if root is None: return for child in root.children: order(child) self.res.append(root.val) order(root) return self.res # 迭代的解法 class Solution: def postorder(self, root: 'Node') -> List[int]: res = list() if root is None: return self.res queue = [root] visited = set() while len(queue) > 0: node = queue[-1] if node.children is None or len(node.children) == 0 or node in visited: res.append(node.val) queue.pop() continue for child in reversed(node.children): queue.append(child) visited.add(node) return self.res ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复