剑指offer：按之字形顺序打印二叉树-创新互联

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

创新互联专注为客户提供全方位的互联网综合服务，包含不限于网站制作、做网站、达拉特网络推广、小程序开发、达拉特网络营销、达拉特企业策划、达拉特品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们大的嘉奖；创新互联为所有大学生创业者提供达拉特建站搭建服务，24小时服务热线：18980820575，官方网址：www.cdcxhl.com

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    """
    由于需要打印Z字型，那么我们在遍历整棵树的时候就需要维护一个栈。
    栈中存储的是下一层的节点的逆序，则在访问的时候按照栈的FILO特性就是正确的节点顺序。
    具体来说在打印奇数层的节点的时候，将该节点的【左右】子节点按顺序入栈，
          在打印偶数层的节点的时候，将该节点的【右左】节点按顺序入栈。

    总结：遇到这类问题我们应该先构造一棵二叉树然后按照题目要求模拟一遍，观察出应该使用什么样的数据
         结构，然后再进行编程
    """
    def Print(self, pRoot):
        def helper(root_stack, ans, turns):
            # 递归出口即队列为空
            if not root_stack:
                return
            length = len(root_stack)
            temp = []

            for i in range(length - 1, -1, -1):
                # 对于某个节点，在打印完它的值之后，将其左右子节点先后入队
                temp.append(root_stack[i].val)
                if root_stack[i].left:
                    root_stack.append(root_stack[i].left)
                if root_stack[i].right:
                    root_stack.append(root_stack[i].right)
                # 注意这里我们判断当前层的奇偶性之后再决定是【左右】还是【右左】
                # 由于是对root_stack的最后两个元素进行位置交换，需要小心下标越界问题
                if turns & 1 != 0 and len(root_stack) > length + 1:
                    root_stack[-1], root_stack[-2] = \
                        root_stack[-2], root_stack[-1]

            ans.append(temp)
            helper(root_stack[length:], ans, turns + 1)

        res = []
        if not pRoot:
            return res
        helper([pRoot], res, 0)
        return res

def main():
    root = TreeNode(5)
    root.left = TreeNode(4)
    root.left.left = TreeNode(3)
    root.left.left.left = TreeNode(2)

    solution = Solution()
    print(solution.Print(root))

if __name__ == '__main__':
    main()

另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

新闻名称：剑指offer：按之字形顺序打印二叉树-创新互联
文章URL：http://www.cdkjz.cn/article/dejsco.html