题目描述

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

知识点

二叉树，栈

Qiang的思路

这道题和面试题32.2相比，多了分行输出时方向不同的要求。对于这个要求，考虑到遍历完一层节点之后下一层第一个要遍历的节点时上一层最后节点的孩子节点，所以想到了使用栈这个数据结构。由于不同的输出顺序，所以维护了两个栈。第一个栈从左到右存储节点，第二个栈从右到左存储。交替循环知道两个栈都为空的时候结束。

# -*- 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==None:
            return []
        result=[]
        s1=[pRoot]
        s2=[]
        while s1!=[] or s2!=[]:
            result.append([])
            if s1!=[]:
                while s1!=[]:
                    node=s1.pop(-1)
                    result[-1].append(node.val)
                    if node.left!=None:
                        s2.append(node.left)
                    if node.right!=None:
                        s2.append(node.right)
            else:
                while s2!=[]:
                    node=s2.pop(-1)
                    result[-1].append(node.val)
                    if node.right!=None:
                        s1.append(node.right)
                    if node.left!=None:
                        s1.append(node.left)
        return result