二叉树专题-lintcode二叉树的层序遍历

  层序遍历算是遍历方式中，比较容易掌握的，实质就是宽度优先遍历，BFS的基本代码块如下;

void BFS(){
  创建队列
  第一个元素入队
  while(队列非空){
  取队首元素top
  出队
  访问top
  下一层的元素按顺序入队
  }
}

  我们来看看题目考察的方式

由以上的分析，容易想到先取到这一层的元素的个数,然后在里面加一层循环即可

vector<vector<int>> levelOrder(TreeNode *root) {
        // write your code here
        queue<TreeNode *> q;
        vector<vector<int>> result;
        if(root==NULL) return result;
        if(root){//不为空则入队
            q.push(root);
            while(!q.empty()){
                vector<int> oneLevel;
                int size = q.size();
                for(int i=0;i<size;++i){
                    TreeNode *node=q.front();
                    q.pop();
                    oneLevel.push_back(node->val);
                    if(node->left) q.push(node->left);
                    if(node->right)q.push(node->right);
                }
                result.push_back(oneLevel);
            }
        }
        return result;
    }

  第一道要求，返回从下往上遍历的结果；我们只需要按照最初的从上向下的遍历，得到[  [3],[9,20],[15,7]  ]后reverse一下即可

  第二道题要求锯齿形的遍历，先从左往右，后从右往左，故只需要设置一个标志位，当从右往左时，我们对这一层的结果reverse即可

  给出锯齿形遍历的代码:

 vector<vector<int>> zigzagLevelOrder(TreeNode * root) {
        // write your code here
         vector<vector<int>> result;
        if(!root) return result;
        queue<TreeNode*> q;
        q.push(root);
        bool leftToRight=true;
        while(!q.empty()){
            vector<int> oneLevel;
            int size=q.size();
            for(int i=0;i<size;++i){
                TreeNode* node=q.front();
                q.pop();
                oneLevel.push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            if(!leftToRight) reverse(oneLevel.begin(),oneLevel.end());
            result.push_back(oneLevel);
            leftToRight=!leftToRight;
        }
        return result;
    }