LeetCode 366 Find Leaves of Binary Tree

LeetCode

Given the root of a binary tree, collect a tree’s nodes as if you were doing this:

Collect all the leaf nodes. Remove all the leaf nodes.
Repeat until the tree is empty.

Example 1:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

Example 2:

Input: root = [1]
Output: [[1]]

Constraints: The number of nodes in the tree is in the range [1, 100].
* -100 <= Node.val <= 100

题目大意：

求逐层叶子剥离的所有叶子节点，按剥离顺序放入结果

解题思路：

考虑BFS从上到下，但深度不对，因为是从叶子节点开始计算的，如例子所示，根节点1的高度取决于儿子的最大深度。所以应该从底到上计算，也就是DFS

解题步骤：

N/A

注意事项：

1. 从底到上计算高度，取左右树的最大高度

Python代码：

def findLeaves(self, root: TreeNode) -> List[List[int]]:
	res = []
	self.dfs(root, res)
	return res

def dfs(self, root, res):
	if not root:
		return 0
	if not root.left and not root.right:
		if len(res) == 0:
			res.append([root.val])
		else:
			res[0].append(root.val)
		return 1
	left_depth = self.dfs(root.left, res)
	right_depth = self.dfs(root.right, res)
	depth = max(left_depth, right_depth) + 1
	if depth - 1 < len(res):
		res[depth - 1].append(root.val)
	else:
		res.append([root.val])
	return depth

算法分析：

时间复杂度为O(n)，空间复杂度O(1)