剑指Offer(五十九):按之字顺序打印二叉树

  • A+
所属分类:剑指Offer
摘要

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

剑指Offer(五十九):按之字顺序打印二叉树

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

剑指Offer(五十九):按之字顺序打印二叉树

按之字顺序打印上图二叉树,打印顺序为:

1

3 2

4 5 6 7

15 14 13 12 12 10 9 8

为了达到这样打印的效果,我们需要使用两个栈。我们在打印某一行结点时,把下一层的子结点保存到相应的栈里。如果当前打印的是奇数层(第一层、第三层等),则先保存左子树结点再保存右子树结点到第一个栈里。如果当前打印的是偶数层(第二层、第四层等),则则先保存右子树结点再保存左子树结点到第二个栈里。

剑指Offer(五十九):按之字顺序打印二叉树

详细步骤,如上图所示。

2、代码

C++:

Jack Cui
阿里云ECS

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: