###### tags: `Leetcode` `medium` `tree` `bfs` `python`

# 107. Binary Tree Level Order Traversal II

## [題目連結] https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

## 題目:
Given the ```root``` of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).


#### [圖片來源:] https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

## 解題想法:
兄弟題目:[102. Binary Tree Level Order Traversal](/uzzm6rKYT0iLgackHNRl5A)

* 題目為給一binary tree，求出bottom-up level order traversal
* 使用bfs，每層進行遍歷
* Interactive
* Recursive
* Python對於反轉:
* 用res.reverse(): 不會回傳值
* 需要用 res[::-1] or 創建新的list: list(reversed(res))

## Python: Interactive
* 每次紀錄當前的所有node.val與下層的node
* while繼續下一層
* 結果reverse即可

from collections import defaultdict
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res=[]
        que=[root]
        while que:
            curLevel=[]
            nextLevel=[]
            for node in que:
                curLevel.append(node.val)
                if node.left:
                    nextLevel.append(node.left)
                if node.right:
                    nextLevel.append(node.right)
            res.append(curLevel)
            que=nextLevel
        return res[::-1]

root=TreeNode(3)
root.insertLeft(9)
root.insertRight(20)
root.right.insertLeft(15)
root.right.insertRight(7)
root.printTree()

result = Solution()
ans = result.levelOrderBottom(root)
print(ans)

''' 
#sol2
class Solution:
    def levelOrderBottom(self, root):
        if not root:
            return []
        
        ans=defaultdict(list)
        map=[{'level':0, 'node':root}]
        
        while map:
            #要FIFO
            cur=map.pop(0)
            root = cur['node']
            ans[cur['level']].append(root.val)
            if root.left:
                map.append({'level':cur['level']+1, 'node':root.left})
            if root.right:
                map.append({'level':cur['level']+1, 'node':root.right})
        return [ans[i] for i in ans][::-1]

'''

## Python: Recursive
* 使用字典存每層的node
* key=level
* val=list()
* 結果reverse即可

from collections import defaultdict
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        self.res=defaultdict(list)
        self.bfs(root,1)
        return [self.res[key] for key in self.res][::-1]
    def bfs(self,root,level):
        if not root:
            return
        self.res[level].append(root.val)
        self.bfs(root.left,level+1)
        self.bfs(root.right,level+1)

root=TreeNode(3)
root.insertLeft(9)
root.insertRight(20)
root.right.insertLeft(15)
root.right.insertRight(7)
root.printTree()

result = Solution()
ans = result.levelOrderBottom(root)
print(ans)