Binary Tree Level Order Traversal II
Created: September 13, 2018 by [lek-tin]
Last updated: September 13, 2018
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]
]
Solution
# 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):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []
def traverse(root, level):
if root != None:
if len(res) == level:
res.insert(0, [])
res[len(res) - 1 - level].append(root.val)
traverse(root.left, level+1)
traverse(root.right, level+1)
traverse(root, 0)
return res