6/22/2017 - 4:12 AM

## 107. Binary Tree Level Order Traversal II

1. Binary Tree Level Order Traversal II
``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root == None:
return []
self.res = []
self.DFS(root, 1)
return self.res[::-1]
def DFS(self, node, level):
if node == None:
return
if len(self.res) < level:
self.res.append([])
self.res[level-1].append(node.val)
self.DFS(node.left, level+1)
self.DFS(node.right, level+1)``````

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/#/description

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).

For example: Given binary tree `[3,9,20,null,null,15,7]`,

``````    3
/ \
9  20
/  \
15   7
``````

return its bottom-up level order traversal as:

``````[
[15,7],
[9,20],
[3]
]
``````