leetcode || 107、Binary Tree Level Order Traversal II

problem：

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.

Hide Tags   Tree Breadth-first Search 題意：層序周遊二叉樹，從最後一層往上開始按層輸出

thinking：

和普通的二叉樹層序周遊原理一樣，借助queue實作，先得到從上到下的層序周遊結果，再借助stack翻轉一下結果即可

code：

class Solution {
  private:
      vector<vector<int> > ret;
      stack<vector<int> > _stack;
  public:
      vector<vector<int> > levelOrderBottom(TreeNode *root) {
          ret.clear();
          if(root==NULL)
              return ret;
          queue<TreeNode *> tmp_queue;
          tmp_queue.push(root);
          level_order(tmp_queue);
          while(!_stack.empty())
          {
              vector<int> tmp=_stack.top();
              ret.push_back(tmp);
              _stack.pop();
          }
          return ret;
      }
      void level_order(queue<TreeNode *> queue1)
      {
          if(queue1.empty())
              return;
          vector<int> array;
          queue<TreeNode *> queue2;
          while(!queue1.empty())
          {
              TreeNode *tmp=queue1.front();
              array.push_back(tmp->val);
              queue1.pop();
              if(tmp->left!=NULL)
                  queue2.push(tmp->left);
              if(tmp->right!=NULL)
                  queue2.push(tmp->right);
          }
          _stack.push(array);
          level_order(queue2);
      }
  };