（二十七）二叉树的ZigZag打印

56 阅读 0 评论 37 点赞

我是靠谱客的博主彩色小白菜，最近开发中收集的这篇文章主要介绍（二十七）二叉树的ZigZag打印，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二叉树的ZigZag打印
在这里插入图片描述

解题思路：（双端队列）

首先生成一个双端队列dq。把头部放入dq；
原则一：如果从左往右打印，那么一律从dq的头部弹出节点，如果弹出的节点有子节点，先让左孩子从尾部进入dq，再让右孩子从尾部进入dq；如果弹出的节点没有子节点，则不需要放dq中。
原则二：如果从右往左打印，那么一律从dq的尾部弹出节点，如果弹出的节点有子节点，先让右孩子从头部进入dq，再让左孩子从头部进入dq；如果弹出的节点没有子节点，则不需要放dq中。
确定切换原则一与原则二的时机：下一层中最后打印的节点是当前层中有子节点的节点中最先进入队列的子节点。此节点也是切换原则的时机，用标签标记即可

在这里插入图片描述

void printLevelAndOrientation(int level,bool lr);

void printByZigzag(TreeNode* head){
    if(head == NULL) return ;
    deque<TreeNode*> dq;
    int level = 1;
    bool lr = true;
    TreeNode *last = head,*nlast = NULL,*cur = head;
    dq.push_front(cur);
    printLevelAndOrientation(level++,lr);
    while(!dq.empty()){
        if(lr){
            cur = dq.front();
            dq.pop_front();
            if(cur->left != NULL){
                nlast = nlast == NULL ? cur->left : nlast;
                dq.push_back(cur->left);
            }
            if(cur->right != NULL){
                nlast = nlast == NULL ? cur->right : nlast;
                dq.push_back(cur->right);
            }
        }else{
            cur = dq.back();
            dq.pop_back();
            if(cur->right != NULL){
                nlast = nlast == NULL ? cur->right : NULL;
                dq.push_front(cur->right);
            }
            if(cur->left != NULL){
                nlast = nlast == NULL ? cur->left : NULL;
                dq.push_front(cur->left);
            }
        }

        cout << cur->value << " ";

        if(cur == last && !dq.empty()){
            lr = !lr;
            last = nlast;
            nlast = NULL;
            cout << endl;
            printLevelAndOrientation(level++,lr);
        }
    }
    cout << endl;
}

void printLevelAndOrientation(int level,bool lr){
    cout << "level " << level << " from " ;
    cout << (lr ? "left to right: " : "right to left: ");        
}

【测试】

#include <iostream>
#include <deque>
using namespace std;

/*树的节点*/
struct TreeNode{
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val): value(val),left(NULL),right(NULL){}
};

TreeNode* createTree(){
    TreeNode* head = new TreeNode(1);
    head->left = new TreeNode(2);
    head->right = new TreeNode(3);
    head->left->left = new TreeNode(4);
    head->left->right = new TreeNode(5);
    head->right->left = new TreeNode(6);
    head->right->right = new TreeNode(7);

    return head;
}


void printLevelAndOrientation(int level,bool lr);
void printByZigzag(TreeNode* head);

int main{
	createTree();
    cout << "print-by-zigzag:" << endl;
    printByZigzag(head);
    return 0;
}