#BIGO二面面试题

[MyLinChi]

问题

层次蛇形遍历二叉树。

求解

ps:之前用了栈+队列的方式，面试官说可读性差。
双端队列

#include <iostream>
#include <vector>
#include<queue>
#include<stack>
#include <numeric>
#include<string>
#include<sstream>
#include <limits>

using namespace std;

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node(int val) :val(val), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    bool flag;
public:
    void travelTree(Node* root) {
        deque<Node*> dq;
        dq.push_back(root);
        int nums = 1;
        int cnt = 0; //currrent node's number
        flag = true;
        for (; !dq.empty();) {
            if (++cnt > nums) {
                flag = !flag;
                cnt = 1;
                nums = dq.size();
            }
            if (flag) { //from left to right
                Node* cur = dq.front();
                cout << cur->val << " ";
                dq.pop_front();
                if (cur->left)dq.push_back(cur->left);
                if (cur->right)dq.push_back(cur->right);
            }
            else {      //from right to left
                Node* cur = dq.back();
                cout << cur->val << " ";
                dq.pop_back();
                if (cur->right)dq.push_front(cur->right);
                if (cur->left)dq.push_front(cur->left);
            }
        }
    }
};

int main() {
    Solution sol;
    Node* tree = new Node(1);
    tree->left = new Node(2);
    tree->left->left = new Node(4);
    tree->left->right = new Node(5);
    tree->right = new Node(3);
    tree->right->left = new Node(6);
    tree->right->right = new Node(7);
    sol.travelTree(tree);                  
    return 0;

}