题目链接：Binary Tree Level Order Traversal II

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,#,#,15,7},

    3 
   / \ 
  9  20 
    /  \ 
   15   7

return its bottom-up level order traversal as:

[ 
  [15,7], 
  [9,20], 
  [3] 
]

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

1 / \ 2 3 / 4 \ 5

The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

这道题的要求是从下往上分层遍历二叉树。

和Binary Tree Level Order Traversal同样的思路，只不过在最后需要将数组反转即可。

由于需要把每层的节点分别放入到数组中，因此需要引入变量n记录每层的节点数量。剩下的，就是广度优先搜索的方法了。

广度优先搜索算法（Breadth First Search），又叫宽度优先搜索，或横向优先搜索。从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。借助队列数据结构，由于队列是先进先出的顺序，因此可以先将左子树入队，然后再将右子树入队。这样一来，左子树结点就存在队头，可以先被访问到。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution
{
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root)
    {
        vector<vector<int> > vvi;
        
        if(NULL == root)
            return vvi;
        
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty())
        {
            vector<int> vi;
            for(int i = 0, n = q.size(); i < n; ++ i)
            {
                TreeNode *temp = q.front();
                q.pop();
                if(temp -> left != NULL)
                    q.push(temp -> left);
                if(temp -> right != NULL)
                    q.push(temp -> right);
                vi.push_back(temp -> val);
            }
            vvi.push_back(vi);
        }
        reverse(vvi.begin(), vvi.end());
        return vvi;
    }
};