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]]
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def levelOrderBottom(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if not root: return [] q = [root] ans = [] while q: ans.append([n.val for n in q]) q = [n for node in q for n in (node.left, node.right) if n] return ans[::-1]
上面解法是层序遍历，使用先序遍历，递归：
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def levelOrderBottom(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ def dfs(node, paths, depth): if not node: return if len(paths) == depth: paths.append([]) paths[depth].append(node.val) dfs(node.left, paths, depth+1) dfs(node.right, paths, depth+1) ans = [] dfs(root, ans, 0) return ans[::-1]