LeetCode 107. Binary Tree Level Order Traversal II

'''

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

'''


# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None


class Solution:

    def levelOrderBottom(self, root: 'TreeNode') -> 'List[List[int]]':

        if not root:

            return []

       

        def btt(i, root):

            if root:

                n = len(self.result)

                if i < -n:

                    self.result.insert(-n, [])

                self.result[i].append(root.val)

                if root.left:

                    btt(i-1, root.left)

                if root.right:

                    btt(i-1, root.right)

       

        self.result = []

        btt(-1,root)



        return self.result