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

Solutions

  类似于分行打印,只不过各一次反过来打印一次:

# -*- 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 []
        res = []
        queue = [pRoot]
        b_left_to_right = 0
        while queue:
            level = []
            size = len(queue)
            for i in range(size):
                node = queue.pop(0)
                level.append(node.val)
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
            if b_left_to_right & 1:
                level = level[::-1]
            b_left_to_right += 1
            res.append(level)
        return res
# 运行时间:21ms
# 占用内存:5728k

  剑指 Offer 的解法,尚未细看:

# -*- 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 not pRoot:
            return []
        res=[]
        nodes=[pRoot]
        right=True
        
        while nodes:
            curStack,nextStack=[],[]
            if right:
                for node in nodes:
                    curStack.append(node.val)
                    if node.left:
                        nextStack.append(node.left)
                    if node.right:
                        nextStack.append(node.right)
            else:
                for node in nodes:
                    curStack.append(node.val)
                    if node.right:
                        nextStack.append(node.right)
                    if node.left:
                        nextStack.append(node.left)
            res.append(curStack)
            nextStack.reverse()
            right=not right
            nodes=nextStack
        return res

References

  1. 061. 按之字形顺序打印二叉树