欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-15 23:27:30
...

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

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

  放到二叉树的遍历中来看,首先根节点入队,根出队,访问根节点,再入队左孩子,入队右孩子;这样再出队时,就是访问的第二层的左侧......以此类推

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

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

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

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;
    }

再来看看其他的要求:

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

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


  第一道要求,返回从下往上遍历的结果;我们只需要按照最初的从上向下的遍历,得到[  [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;
    }