Leetcode 103: 二叉树的锯齿形层序遍历

2021年3月14日 254Browse 0Like 0Comments

题目描述

给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

例如:
给定二叉树 [3,9,20,null,null,15,7],

3

/ \
9 20
/ \
15 7
返回锯齿形层序遍历如下:

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

解题思路

这道题是二叉树层次遍历的变种,可以参照二叉树遍历大总结里面的层次遍历中的方法进行微改动。

由于我们已经加上了level来指示二叉树的层数,那么我们其实只要判断level为奇数的时候,将存储那一层结点值的vector颠倒再加入两层vector就可以了

代码示例

    void levelOrder(TreeNode* root,vector<vector<int>>&res,int lev)
    {
        if(root==nullptr) return ;
        queue<TreeNode*>q;
        q.push(root);
        while(!q.empty())
        {
            int size=q.size();
            vector<int>level;
            for(int i=0;i<size;i++)
            {
                TreeNode* node=q.front();
                q.pop();
                if(node==nullptr) continue;
                level.push_back(node->val);
                q.push(node->left);
                q.push(node->right);
            }
            if(lev%2==1) reverse(level.begin(),level.end());
            lev++;
            if(level.size()>0) res.push_back(level);

        }
    }
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>>res;
        levelOrder(root,res,0);
        return res;

    }

agedcat_xuanzai

这个人很懒,什么都没留下

Comments