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

  • 3
  • 222 °C
  • 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

发表评论

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

目前评论:3   其中:访客  2   博主  1

    • avatar 爱看的剧 来自天朝的朋友 谷歌浏览器 Mac OS X 10_12_6 上海市 上海理工大学 4

      第i层先入,则第i-1层节点先出,故用栈;层之间交替输出,故用两个栈。

      • avatar 爱看的剧 来自天朝的朋友 谷歌浏览器 Mac OS X 10_12_6 上海市 上海理工大学 4

        line25:不需要判断s[0].top()非空吗?即if(s[0].top() && s[0].top()->left != NULL)

          • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 百度网讯科技联通节点

            @爱看的剧 while的时候已经判断了。