[剑指Offer]按之字形顺序打印二叉树

题目描述

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

解题思路

将层次遍历用二维列表存储起来，最后根据二维列表的索引选择正序输出还是逆序输出。

代码

Python(2.7.3)

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        # write code here
        if pRoot is None:
            return []
        queue = [pRoot]
        res_list = []
        while queue:
            tmp_queue = []
            tmp_queue_val = []
            for tmp in queue:
                tmp_queue_val.append(tmp.val)
                if tmp.left is not None:
                    tmp_queue.append(tmp.left)
                if tmp.right is not None:
                    tmp_queue.append(tmp.right)
            queue = tmp_queue
            res_list.append(tmp_queue_val)
        res = []
        for idx, i in enumerate(res_list):
            if idx % 2 == 0:
                res.append(i)
            else:
                res.append(i[::-1])
        return res

运行时间：24ms
占用内存：5748k