leetcode107 Binary Tree Level Order Traversal II

 1 """
 2 层次遍历
 3 """
 4 """
 5 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).
 6 For example:
 7 Given binary tree [3,9,20,null,null,15,7],
 8     3
 9    / 
10   9  20
11     /  
12    15   7
13 return its bottom-up level order traversal as:
14 [
15   [15,7],
16   [9,20],
17   [3]
18 ]
19 """
20 
21 class TreeNode:
22     def __init__(self, x):
23         self.val = x
24         self.left = None
25         self.right = None
26 
27 class Solution:
28     def levelOrderBottom(self, root):
29         if root == None:
30             return []
31         queue = []
32         res = []
33         queue.append(root)
34         while queue:
35             n = len(queue)  #!!!记录每一层有几个结点
36             newqueue = []   #存储当前层
37             for _ in range(n):
38                 x = queue.pop(0)  #pop()弹出最后一个元素, pop(0)弹出第一个元素
39                 newqueue.append(x.val) #bug newqueue.append(x),这里只存值就可以了
40                 if x.left:
41                     queue.append(x.left)
42                 if x.right:
43                     queue.append(x.right)
44                #bug wrong answer   res.append(newqueue)
45             res.insert(0,newqueue)  #插入到尾部
46             #aList = [123, 'xyz', 'zara', 'abc']
47             #aList.insert( 3, 2009) (索引,数值)
48             #[123, 'xyz', 'zara', 2009, 'abc']
49         return res