leetcode-107-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,null,null,15,7],
3
/
9 20
/
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]

给定一棵二叉树，返回从底至顶的层次遍历结果。

利用一个辅助队列完成BFS.再反向存储数组即可。

/**

• Definition for a binary tree node.
• struct TreeNode {
• int val;
• TreeNode *left;
• TreeNode *right;
• TreeNode(int x) : val(x), left(NULL), right(NULL) {}
• };
  */
  class Solution {
  public:

  vector<vector<int>> levelOrderBottom(TreeNode* root) {
      vector<int> tem;
      vector<vector<int>> ans;
      queue <TreeNode*> q;
      if(!root) return ans;
      q.push(root);
      q.push(NULL);
      while(!q.empty())
      {
          TreeNode * t = q.front();
          q.pop();
          if(t){
              tem.push_back(t->val);
              if(t->left)
              q.push(t->left);
              if(t->right)
              q.push(t->right);
          }else
          {
              if(!q.empty()){
              ans.push_back(tem);
              tem.clear();
              q.push(NULL);}
              else
              ans.push_back(tem);
          }
      }
      vector<vector<int>> res;
      for(int i=ans.size()-1;i>=0;i--)
      res.push_back(ans[i]);
      return res;
  }
  

  };