[LeetCode] 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},

/ \

9 20

/ \

15 7

return its bottom-up level order traversal as:

[

[15,7]

[9,20],

[3],

]

问题描述：给定一个二叉树，从下往上层次遍历所有节点。

可以以层次遍历二叉树，将每层的节点值保存在vector容器中，再将vector容器保存在一个栈中，遍历完成后，将栈中的vector保存到另一个vector中。

class Solution {  
public:  
    vector<vector<int> > levelOrderBottom(TreeNode *root) {  
        // Note: The Solution object is instantiated only once and is reused by each test case.  
         if(root == NULL)  
            return vector<vector<int> >(0);  
  
        queue<pair<TreeNode *, int> > que;  
        stack<vector<int> > sta;  
        vector<int> ivec;  
  
        TreeNode *pnode = root;  
        int level = 0;  
        pair<TreeNode *, int> pair_data;  
        que.push(make_pair(pnode, 1));  
        while(!que.empty()) {  
            pair_data = que.front();  
            que.pop();  
            pnode = pair_data.first;  
            level = pair_data.second;  
            ivec.push_back(pnode->val);  
            if(que.empty() || level != que.front().second) {  
                sta.push(ivec);  
                ivec.clear();  
            }  
            if(pnode->left) {  
                que.push(make_pair(pnode->left, level+1));  
            }  
            if(pnode->right) {  
                que.push(make_pair(pnode->right, level+1));  
            }  
        }  
  
        vector<vector<int> > vec;  
        while(!sta.empty()) {  
            ivec = sta.top();  
            vec.push_back(ivec);  
            sta.pop();  
        }  
        return vec;  
    }  
};

补充：软件开发 , C++ ,