题目

题解

二叉树结构如下：

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

1.迭代法

class Solution {//和#102类似，有所改变，有迭代法和递归法两种方法迭代。1 迭代（改变插入顺序）
                //迭代分为直接翻转数组和改变插入顺序两种方式，翻转数组效率不高，谢哥改变插入顺序
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;//定义保存结果的数组
        if(!root) return res;//特殊情况直接返回
        queue<TreeNode*> q;//定义队列
        q.push(root);//先把根节点加入队列
        int levelNum = 0;//定义当前遍历的层数
        while(!q.empty()){//当q不为空时，继续迭代
            vector<int> thisLevel;//定义存储当前一行的数组
            for(int i = q.size(); i>0; i--){//这一块和#102类似
                TreeNode *cur = q.front();q.pop();//取队首的值，并出队
                if(levelNum%2==0) thisLevel.push_back(cur->val);//偶数行在数组尾部加值
                else thisLevel.insert(thisLevel.begin(),cur->val);//奇数行在数组头部加值
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);//队列加入两个子节点
            }
            res.push_back(thisLevel);//该行数组加入结果中
            levelNum++;//行数++
        }
        return res;
    }
};

2. 递归法

class Solution {//和#102类似，有所改变，有迭代法和递归法两种方法迭代。2 递归法

vector<vector<int>> res;//定义私有变量存储结果
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(!root) return res;//特殊情况直接返回
        int levelNum = 0;
        helper(root,levelNum);//调用递归函数
        return res;//返回结果
    }

    void helper(TreeNode* cur, int level){
        if(!cur) return;//特殊情况直接返回
        if(res.size() <= level) res.push_back({});//这一步与#102一样，判断何时需要增加新的一行
        if(level%2==0) res[level].push_back(cur->val);//偶数行在末尾加数
        else res[level].insert(res[level].begin(),cur->val);//奇数行在数组头加数
        helper(cur->left,level+1);
        helper(cur->right,level+1);//递归左右子树
    }
};