面试题32

题目地址：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/

题目描述

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

题目示例

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

　　　  3
　　　/   
　　 9    20
　　　　/   
　　　  15  7
返回其层次遍历结果：

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

解题思路

思路1（BFS，即普通队列queue）：利用bool值flag来区分奇偶层，当flag=true时，从左往右遍历，否则，从右往左遍历，BFS中我们默认从左往右遍历，那么如何从右往左如何遍历呢?我们只需要将存储该层节点的数组arr翻转一下就可以了。

思路2（双端队列deque）：此题与第32题其它两个变版不一样，涉及到了奇偶层不同的遍历方式，观察题目可以发现，二叉树的奇数层从左往右打印节点，而偶数层则从右往左打印节点，我们可以利用双端队列deque解决此问题。

思路3（队列+栈）：我们使用队列实现二叉树的遍历，然后使用栈翻转每一层节点。

思路4（栈+栈）：我们知道双栈可以实现队列，所以利用栈的后进先出特点解决此问题。其中，两个栈分别存放奇数层、偶数层节点，弹栈的时候，依次将栈顶节点的子节点压入相反的栈，直到两个栈均为空为止。

程序源码

思路1：普通队列queue改进

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr) return {};
        vector<vector<int>> res;
        
        queue<TreeNode* > q;
        q.push(root);
        bool flag = true; //默认从左往右遍历，即flag=true，当flag=false时，从右往左遍历
        while(!q.empty())
        {
            vector<int> arr;
            int level_node = q.size();
            for(int i = 0; i < level_node; i++)
            {
                TreeNode* node = q.front();
                arr.push_back(node->val);
                q.pop();
                if(node->left != nullptr) q.push(node->left);
                if(node->right != nullptr) q.push(node->right);
            }
            if(flag == false) reverse(arr.begin(), arr.end()); //奇数层，翻转节点，从右往左遍历
            flag = !flag; //更新flag值，遍历下一层节点
            res.push_back(arr);
        }
        return res;
    }
};

 思路2：双端队列deque

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr) return {};
        vector<vector<int>> res;
        deque<TreeNode* > q;
        q.push_back(root);
        bool flag = true; //默认从左往右遍历，即flag=true，当flag=false时，从右往左遍历
        while(!q.empty())
        {
            vector<int> arr;
            int level_node = q.size();
            TreeNode* node;
            for(int i = 0; i < level_node; i++)
            {
                if(flag == true)
                {
                    node = q.front(); //从左往右遍历，即从每层第一个节点取
                    arr.push_back(node->val); //存放该层节点
                    q.pop_front(); //从左边取，右边放
                    if(node->left != nullptr) q.push_back(node->left); //放左边节点
                    if(node->right != nullptr) q.push_back(node->right); //放右边节点
                }
                else
                {
                    node = q.back(); //从右往左遍历，即从每层最后一个节点取
                    arr.push_back(node->val); //存放该层节点
                    q.pop_back(); //从右边取，左边放
                    if(node->right != nullptr) q.push_front(node->right); //放右边节点
                    if(node->left != nullptr) q.push_front(node->left); //放左边节点
                }
            }
            flag = !flag; //更新flag值，遍历下一层节点
            res.push_back(arr);
        }
        return res;
    }
};

思路3：”队列+栈“双剑合璧

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr) return {};
        vector<vector<int>> res;
        queue<TreeNode* > q;
        stack<TreeNode* > s;
        q.push(root);
        bool flag = true; //默认从左往右遍历，即flag=true，当flag=false时，从右往左遍历
        while(!q.empty())
        {
            vector<int> arr;
            int level_node = q.size();
            for(int i = 0; i < level_node; i++)
            {
                TreeNode* node = q.front();
                arr.push_back(node->val);
                q.pop();
                if(flag == true) //偶数层从左往右遍历
                {
                    if(node->left != nullptr) s.push(node->left);
                    if(node->right != nullptr) s.push(node->right);
                }
                else //奇数层从右往左遍历
                {
                    if(node->right != nullptr) s.push(node->right);
                    if(node->left != nullptr) s.push(node->left);
                }
            }
            while(!s.empty())
            {
                q.push(s.top()); //翻转加入队列q
                s.pop();
            }
            flag = !flag; //更新flag值，遍历下一层节点
            res.push_back(arr);
            arr.clear(); //清空数组中存放的节点
        }
        return res;
    }
};

思路4：栈+栈

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr) return {};
        vector<vector<int>> res;
        stack<TreeNode* > s1; //存放奇数层节点
        stack<TreeNode* > s2; //存放偶数层节点
        s1.push(root);
        bool flag = true; //默认从左往右遍历，即flag=true，当flag=false时，从右往左遍历
        while(!s1.empty() || !s2.empty())
        {
            vector<int> arr;
            if(flag == true) //奇数层
            {
                while(!s1.empty()) //清空栈s1，依次将节点压入栈s2（先左后右）
                {
                    TreeNode* node = s1.top();
                    arr.push_back(node->val);
                    s1.pop();
                    if(node->left != nullptr) s2.push(node->left);
                    if(node->right != nullptr) s2.push(node->right);
                }
            }
            else //偶数层
            {
                while(!s2.empty()) //清空栈s2，依次将节点压入栈s1（先右后左）
                {
                    TreeNode* node = s2.top();
                    arr.push_back(node->val);
                    s2.pop();
                    if(node->right != nullptr) s1.push(node->right);
                    if(node->left != nullptr) s1.push(node->left);
                }
            }
            flag = !flag; //更新flag值，遍历下一层节点
            res.push_back(arr);
        }
        return res;
    }
};