https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
Binary Tree Level Order Traversal II
Total Accepted: 56136 Total Submissions: 177858 Difficulty: Easy
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,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[ [15,7], [9,20], [3] ]
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
Code (Using dfs recursion)
# 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]]
"""
res = []
self.dfs(root, 0, res)
return res
def dfs(self, root, level, res):
if root:
if len(res) < level+1:
res.insert(0, [])
res[~level].append(root.val)
self.dfs(root.left, level+1, res)
self.dfs(root.right, level+1, res)
Code (Using bfs + deque)
from collections import *
# 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]]
"""
res = []
q = deque([(root, 0)])
while q:
node, level = q.popleft()
if node:
if len(res) < level+1:
res.insert(0, [])
res[~level].append(node.val)
q.append((node.left, level+1))
q.append((node.right, level+1))
return res
Idea
Either for dfs or bfs, you make sure that the elements more leftmost in the same level will be visited earlier than the elements more rightmost in that level. Here `~level` is equivalent to `-level-1`. (ref: http://stackoverflow.com/questions/8305199/the-tilde-operator-in-python)