程序员代码面试指南 3.9：二叉树按层打印与ZigZag打印

1、思路

• 模板题，就是二叉树的层序遍历和锯齿形遍历；

• 输出比较麻烦。

2、代码

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;

    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

//建树
void createTree(TreeNode *root, int &n)
{
    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    root->val = rootVal;

    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left, -- n);
    }

    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right, -- n);
    }
}

//层序遍历
void printByLevel(TreeNode *root)
{
    queue<TreeNode*> q;
    q.push(root);

    int level = 1;
    while (!q.empty())
    {
        int size = q.size();

        cout << "Level " << level << " : ";
        while (size -- )
        {
            TreeNode *cur = q.front();
            q.pop();

            cout << cur->val << " ";

            if (cur->left != nullptr) q.push(cur->left);
            if (cur->right != nullptr) q.push(cur->right);
        }

        ++ level;
        cout << endl;
    }
}

// Z 字形遍历
void printByZigZag(TreeNode *root)
{
    queue<TreeNode*> q;
    q.push(root);

    int level = 1;
    bool flag = true;

    while (!q.empty())
    {
        vector<int> tmp;
        int size = q.size();

        if (flag)
        {
            cout << "Level " << level << " from left to right: ";
        }
        else
        {
            cout << "Level " << level << " from right to left: ";
        }

        while (size -- )
        {
            TreeNode *cur = q.front();
            q.pop();
            tmp.push_back(cur->val);

            if (cur->left != nullptr) q.push(cur->left);
            if (cur->right != nullptr) q.push(cur->right);
        }

        if (!flag) reverse(tmp.begin(), tmp.end());     //反转当前层

        for (int num : tmp) cout << num << " ";
        cout << endl;

        flag ^= 1;
        ++ level;
    }
}

int main()
{
    int n, rootVal;
    cin >> n >> rootVal;

    TreeNode *root = new TreeNode(rootVal);
    createTree(root, n);

    printByLevel(root);
    printByZigZag(root);

    return 0;
}