Binary|Binary Tree Level Order Traversal II二叉树之层级次序2 BinaryTreeLevelOrderTraversalII二叉树

Easy 给定二叉树，返回从下至上层级遍历的节点值(从左往右，从叶到根)

Example:
二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回:
[
[15,7],
[9,20],
[3]
]

此题是典型的DFS(depth-first search)算法题。可以使用递归的办法：

根节点level为0，寻找根节点的值，加入响应res

更新根节点level，对根节点的左分支和右分支分别找根节点。

这里的关键是通过根节点的level来控制左右往下遍历的时能够同步推进。因为此题要从下往上输出，需要对结果进行reverse。

# 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]] """ res = [] self.dfs(root,0,res) return resdef dfs(self, root, level, res): if root: if len(res) < level + 1: res.insert(0,[]) res[-(level+1)].append(root.val) self.dfs(root.left,level+1,res) self.dfs(root.right,level+1,res)

dfs+stack 下面是另外一种解决方案，直接利用stack。

def levelOrderBottom2(self, root): stack = [(root, 0)] res = [] while stack: node, level = stack.pop() if node: if len(res) < level+1: res.insert(0, []) res[-(level+1)].append(node.val) stack.append((node.right, level+1)) stack.append((node.left, level+1)) return res

bfs + queue 【Binary|Binary Tree Level Order Traversal II二叉树之层级次序2】下面是第三者解决办法，利用queue。

def levelOrderBottom(self, root): queue, res = collections.deque([(root, 0)]), [] while queue: node, level = queue.popleft() if node: if len(res) < level+1: res.insert(0, []) res[-(level+1)].append(node.val) queue.append((node.left, level+1)) queue.append((node.right, level+1)) return res