二叉树层序遍历，输出时每一层的节点值要分开存，按第N、N-1、N-2...二、一层的顺序
Python BFS版（BFS的时候按层数升序记录，最后列表反转一下）
1 #107
2 #Runtime: 19 ms
3 #Memory Usage: 13.8 MB
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def levelOrderBottom(self, root):
13 """
14 :type root: TreeNode
15 :rtype: List[List[int]]
16 """
17 if not root:
18 return []
19 q = []
20 ans = []
21 q.append(root)
22 ans.append([root.val])
23 while q:
24 sz = len(q)
25 ans.append([])
26 for i in range(sz):
27 if q[0].left:
28 q.append(q[0].left)
29 ans[-1].append(q[0].left.val)
30 if q[0].right:
31 q.append(q[0].right)
32 ans[-1].append(q[0].right.val)
33 q.pop(0)
34 if not ans[-1]:
35 ans.pop(-1)
36 ans.reverse()
37 return ans
1 #107
2 #Runtime: 26 ms
3 #Memory Usage: 14.1 MB
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def DFS(self, r, ans, depth):
13 if not r:
14 return
15 while len(ans) < depth + 1:
16 ans.append([])
17 ans[depth].append(r.val)
18 self.DFS(r.left, ans, depth + 1)
19 self.DFS(r.right, ans, depth + 1)
20 return ans[::-1]
21
22 def levelOrderBottom(self, root):
23 """
24 :type root: TreeNode
25 :rtype: List[List[int]]
26 """
27 return self.DFS(root, [], 0)
CPP版
1 //107
2 //Runtime: 40 ms
3
4 /**
5 * Definition for binary tree
6 * struct TreeNode {
7 * int val;
8 * TreeNode *left;
9 * TreeNode *right;
10 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11 * };
12 */
13 class Solution {
14 public:
15 struct Que {
16 TreeNode *pt;
17 int depth;
18 }que[10010];
19 vector<vector<int> > levelOrderBottom(TreeNode *root) {
20 vector<vector<int> > res, ans;
21 if(root == NULL) return res;
22 int l = 0, r = 1, tdepth = 0;
23 que[0].pt = root;
24 que[0].depth = 0;
25 vector<int> tres;
26 tres.push_back(root->val);
27 res.push_back(tres);
28 tres.clear();
29 while(l < r) {
30 TreeNode *tp = que[l].pt;
31 if(tdepth < que[l].depth) {
32 res.push_back(tres);
33 tres.clear();
34 }
35 if(tp->left != NULL) {
36 que[r].pt = tp->left;
37 que[r].depth = que[l].depth + 1;
38 tres.push_back(tp->left->val);
39 ++r;
40 }
41 if(tp->right != NULL) {
42 que[r].pt = tp->right;
43 que[r].depth = que[l].depth + 1;
44 tres.push_back(tp->right->val);
45 ++r;
46 }
47 tdepth = que[l].depth;
48 ++l;
49 }
50 if(!tres.empty()) res.push_back(tres);
51 for(int i = res.size() - 1; i >= 0; --i) ans.push_back(res[i]);
52 return ans;
53 }
54 };