0366：寻找二叉树的叶子节点（★）

2016-01-01 约 226 字预计阅读 1 分钟次阅读

力扣第 366 题

题目

给你一棵二叉树，请按以下要求的顺序收集它的全部节点：

依次从左到右，每次收集并删除所有的叶子节点
重复如上过程直到整棵树为空

示例:

输入: [1,2,3,4,5]

1
/ \
2   3
/ \
4   5

输出: [[4,5,3],[2],[1]]

解释:

1. 删除叶子节点 [4,5,3] ，得到如下树结构：

          1
/
2

2. 现在删去叶子节点 [2] ，得到如下树结构：

3. 现在删去叶子节点 [1] ，得到空树：

[]

分析

观察发现是按节点的高度从小到大收集，因此用递归并返回节点高度即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


def findLeaves(self, root: TreeNode) -> List[List[int]]:
	def dfs(node):
		if not node:
			return -1
		h = 1+max(dfs(node.left), dfs(node.right))
		if h==len(res):
			res.append([])
		res[h].append(node.val)
		return h

	res = []
	dfs(root)
	return res

目录

0366：寻找二叉树的叶子节点（★）

题目

分析

解答