0590：N 叉树的后序遍历

2016-08-12 约 346 字预计阅读 1 分钟次阅读

力扣第 590 题

题目

给定一个 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⁴] 内
0 <= Node.val <= 10⁴
n 叉树的高度小于或等于 1000

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

分析

#1

先写出递归算法，显然，将每个子树的后序遍历、根节点拼接起来即可。

1
2
3
4
5
6
7
8


def postorder(self, root: 'Node') -> List[int]:
	if not root:
		return []
	res = []
	if root.children:
		for child in root.children:
			res.extend(self.postorder(child))
	return res + [root.val]

52 ms

#2

迭代算法和 0144 类似，注意入栈顺序是 [节点值，子树的反序]。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


def postorder(self, root: 'Node') -> List[int]:
	res, stack = [], [root]
	while stack:
		node = stack.pop()
		if isinstance(node, int):
			res.append(node)
		elif node:
			stack.append(node.val)
			if node.children:
				stack.extend(node.children[::-1])
	return res

56 ms

目录

0590：N 叉树的后序遍历

题目

分析

#1

#2

解答