剑指Offer 59. 按之字形顺序打印二叉树 （二叉树）

时间：2021-07-29 09:22:44

题目描述

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

题目地址

https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=13&tqId=11212&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

思路

层次遍历保存结点，最后奇数层翻转

Python 

# -*- coding:utf-8 -*-

class TreeNode:

    def __init__(self, x):

        self.val = x

        self.left = None

        self.right = None

node1 = TreeNode(1)

node2 = TreeNode(2)

node3 = TreeNode(3)

node4 = TreeNode(4)

node5 = TreeNode(5)

node1.left = node2

node1.right = node3

node2.left = node4

node3.right = node5

class Solution:

    def Print(self, pRoot):

        # write code here

        # 层次遍历保存结点，最后奇数层翻转

        ans = []

        if not pRoot:

            return ans

        queue = []

        queue.append(pRoot)

        while queue:

            temp = []

            for i in range(len(queue)):

                r = queue.pop(0)

                temp.append(r.val)

                if r.left:

                    queue.append(r.left)

                if r.right:

                    queue.append(r.right)

            ans.append(temp)

        for i in range(1,len(ans),2):

            ans[i] = ans[i][::-1]

        return ans

if __name__ == '__main__':

    # [[1] [3 2] [4 5]]

    result = Solution().Print(node1)

    print(result)

相关文章