劍指offer：按之字形順序打印二叉樹

題目描述
請實現一個函數按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。

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()