Binary Tree Level Order Traversal I, II(C++ code)

LeetCode Binary Tree Level Order Traversal,Sep 29 
 难度3，出现频率4
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
return its level order traversal as:

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

思路： 辅助数据结构queue，每次从头pop一个node， 后面就push node's children.这里要求每层单存一个list,

所以记得用一个指针last记录每层的最后一个node，每当遍历到last时，更新last为当前queue的末尾。

Code如下：

vector<vector<int>> levelOrder(TreeNode *root){
  vector<vector<int>> res;
  if(!root) return res;
  queue<TreeNode *> myque;
  vector<int> level;
  TreeNode *last = root;
  myque.push(root);

  while(!myque.empty()){
     root = myque.front();
     myque.pop();
     level.push_back(root->val);
    if(root->left) myque.push(root->left);
    if(root->right) myque.push(root->right);
    
    if(root == last) {
     last = myque.back();
     res.push_back(level);
     level.clear();
    }
  }
  
  return res;
} 


Binary Tree Level Order Traversal II, Oct 1 '12
难度3，出现频率1
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],
]

思路： 从上题基本一样，只是每个level存进result的时候，是从头存进去。

vector<vector<int>> levelOrder(TreeNode *root){
  vector<vector<int>> res;
  if(!root) return res;
  queue<TreeNode *> myque;
  vector<int> level;
  TreeNode *last = root;
  myque.push(root);

  while(!myque.empty()){
     root = myque.front();
     myque.pop();
     level.push_back(root->val);
    if(root->left) myque.push(root->left);
    if(root->right) myque.push(root->right);
    
    if(root == last) {
     last = myque.back();
     res.insert(res.begin(),level);
     level.clear();
    }
  }
  
  return res;
}