Can't deny that using bottom-up level tracking is still the most clear solution with the least code, but we can simply use the result list to keep track of which level we are in each recursion. The code is neither fast nor neat, just another way to solve this problem. The steps are:
- Post-order traversal.
- If root is null, return an empty list, which is the result list.
- After getting the two returned lists from the children of root, the current leaf level would be "length_of_the_longer_one + 1", which is the position root should go to. Merge the two lists and append root to the end.
class Solution(object): def findLeaves(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if not root: return  left_list = self.findLeaves(root.left) right_list = self.findLeaves(root.right) merged_list = self.merge_list(left_list, right_list) merged_list.append([root.val]) return merged_list def merge_list(self, list1, list2): if not list1 and not list2: return  if not list1: return list2 if not list2: return list1 # The following code is to make sure we always concatenate right # list to the end of left list to keep the left-to-right order. len1 = len(list1) len2 = len(list2) if len1 >= len2: i = 0 while i < len2: list1[i] += list2[i] i += 1 return list1 k = 0 while k < len1: list2[k] = list1[k] + list2[k] k += 1 return list2
By the way I haven't figured out the time and space complexity of this solution, little help?