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]
]
Python Solution 1:
# 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]]
"""
def preorder(root, level, res):
if not root: return
if len(res) == level:
res.append([])
res[level].append(root.val)
preorder(root.left, level + 1, res)
preorder(root.right, level + 1, res)
res = []
preorder(root, 0, res)
return res[::-1]
Python Solution 2:
# 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 not root: return []
l = [root]
res = []
while l:
res.append([])
r = []
for n in l:
res[-1].append(n.val)
if n.left: r.append(n.left)
if n.right: r.append(n.right)
l = r
return res[::-1]
Summary:
- DFS, BFS
近期评论