Basic Idea: since we strip one layer of leaves at a time, the time when a middle node got stripped is based on the height of its taller children as the taller the children, the later the node got striped. Using a default dictionary, store a list of node values for each height, and construct the solution at the end.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution(object): def findLeaves(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ self.d = collections.defaultdict(list) def dfs(node): """ Returns the height of node, also adds the value of the node to the corresponding height in the dictionary. """ if not node: return -1 else: height = 1 + max(dfs(node.left), dfs(node.right)) self.d[height].append(node.val) return height dfs(root) return [self.d[height] for height in sorted(self.d)] |