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

2018年1月29日10:48:25 5 2,127 °C
摘要

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

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

一、前言

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

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

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

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

1

3 2

4 5 6 7

15 14 13 12 12 10 9 8

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

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

详细步骤,如上图所示。

2、代码

C++:

Python

感谢@小小毛提供python代码及本地测试用例。

weinxin
微信公众号
分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注!
Jack Cui

发表评论

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

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

    • 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的时候已经判断了。

          • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3

            1 按序获取每一层节点的值;
            2. 将偶数层节点的值倒序。
            # -*- coding:utf-8 -*-
            class TreeNode:
            def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
            class Solution:
            “””docstring for Solution”””
            def Print(self, pRoot):
            resultArray = []
            if not pRoot:
            return resultArray
            curLayerNodes = [pRoot]
            isEvenLayer = True
            while curLayerNodes:
            curLayerValues = []
            nextLayerNodes = []
            isEvenLayer = not isEvenLayer
            for node in curLayerNodes:
            curLayerValues.append(node.val)
            if node.left:
            nextLayerNodes.append(node.left)
            if node.right:
            nextLayerNodes.append(node.right)
            curLayerNodes = nextLayerNodes
            resultArray.append(curLayerValues[::-1]) if isEvenLayer else resultArray.append(curLayerValues)
            return resultArray

            if __name__ == ‘__main__’:
            A1 = TreeNode(1)
            A2 = TreeNode(2)
            A3 = TreeNode(3)
            A4 = TreeNode(4)
            A5 = TreeNode(5)
            A6 = TreeNode(6)
            A7 = TreeNode(7)

            A1.left=A2
            A1.right=A3
            A2.left=A4
            A2.right=A5
            A3.left=A6
            A3.right=A7

            solution = Solution()
            ans=solution.Print(A1)
            print(ans)

              • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点

                @小小毛 优秀~!