Python solution without using level tracking


  • 1
    B

    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:

    1. Post-order traversal.
    2. If root is null, return an empty list, which is the result list.
    3. 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?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.