leetcode103-二叉树的锯齿形层序遍历

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

用两个栈来实现。先把根节点放入第一个栈。循环内部根据哪个栈为空判断新的节点放到哪个栈，确定先左还是先右。当两个栈都为空时，循环结束。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //void Tracking(vector<vector<int>> res,TreeNode* root,)
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(root==nullptr) return {};
        stack<TreeNode*> sss1;
        stack<TreeNode*> sss2;
        vector<vector<int>> res;
        sss1.push(root);
        bool flag=true;
        while(!sss1.empty()||!sss2.empty())
        {
            vector<int> temp;
            if(sss2.empty())
            {
                int size=sss1.size();
                for(int i=0;i<size;i++)
                {
                    TreeNode *t=sss1.top();
                    sss1.pop();
                    temp.push_back(t->val);
                    if(t->left) sss2.push(t->left);
                    if(t->right) sss2.push(t->right);
                }
            }
            else if(sss1.empty())
            {
                int size=sss2.size();
                for(int i=0;i<size;i++)
                {
                    TreeNode *t=sss2.top();
                    sss2.pop();
                    temp.push_back(t->val);
                    if(t->right) sss1.push(t->right);
                    if(t->left) sss1.push(t->left);
                }
            }
            res.push_back(temp);
        }
        return res;
    }
};

评论区一个大佬的代码。既然已经知道每个一维数组的大小，那么就没有必要各种反转了。

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(root==nullptr) return {};
        vector<vector<int>> res;
        queue<TreeNode*> sss;
        sss.push(root);
        bool flag=true;
        while(!sss.empty())
        {
            int size=sss.size();
            vector<int> temp(size,0);
            for(int i=0;i<size;i++)
            {
                TreeNode* t=sss.front();
                sss.pop();
                temp[flag?i:size-1-i]=t->val;
                if(t->left) sss.push(t->left);
                if(t->right) sss.push(t->right);
            }
            res.push_back(temp);
            flag=!flag;
        }
        return res;
    }
};