一、题目描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替） 例如：
给定的二叉树是{1,2,3,#,#,4,5}
该二叉树之字形层序遍历的结果是 [ [1], [3,2], [4,5] ]
示例1
输入：{1,2,3,#,#,4,5}
返回值：[[1],[3,2],[4,5]]
示例2
输入：{8,6,10,5,7,9,11}
返回值：[[8],[10,6],[5,7,9,11]]
示例3
输入：{1,2,3,4,5}
返回值：[[1],[3,2],[4,5]]
二、解题思路
（一）层次遍历+栈
主要利用层次遍历二叉树的节点，并根据奇偶层添加二叉树的节点
算法流程：
1、特殊情况：如果树的根节点为空，则直接返回 【】
2、初始化：返回列表 res ，二叉树层索引 index，辅助栈
3、层次遍历循环，当栈为空跳出：
step1：新建列表tmp，用于临时存储当前层打印结果
step2：当前层打印循环：循环次数为当前层节点数量
1、出栈：栈底元素，记为 node
2、打印：将所在层节点值添加到 tmp中
3、添加子节点：若 node 的左右子树不为空，则 入栈
step3：根据index判断所在层是奇数层还是偶数层：
1、若为奇数层：将tmp直接添加到res中
2、若为偶数层：将tmp倒序添加到res中
step4：index 加1
4、返回打印结果 res
class Solution:
def Print(self, pRoot):
# write code here
if not pRoot:
return []
res = []
# 辅助栈
stack = [pRoot]
# 记录层数
index = 1
while stack:
tmp = []
for i in range(len(stack)):
node = stack[0]
stack = stack[1:]
tmp.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
# 判断所在树的层数，根据层数对 tmp 是否倒序存储
if index % 2 == 0:
res.append(tmp[::-1])
else:
res.append(tmp)
index += 1
return res
复杂度分析：
时间复杂度O(N)：N为二叉树的节点数量，层次遍历、进出栈
空间复杂度O(N)： 最差情况下，即当树为满二叉树时，最多有 N/2 个树节点 同时 在 stack 中，使用 O(N) 大小的额外空间。
（二）双栈
一旦看到这种有关顺序的，第一个就要想到用栈或队列实现，有这个思路才能进一步实现、优化。
比如这道题，要求 “第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印”，显然，如果能直接利用栈或队列的特性，就能实现题目要求的各种顺序了。
算法流程：
1、 维护两个栈，一个存放奇数层的节点，一个存放偶数层的节点
2、整型变量level表示当前遍历第几层，奇数则顺序打印，偶数逆序打印, 从第1层开始
3、分奇数层和偶数层处理
（1）奇数层按顺序，每次偶数层的栈保存偶数层节点，先存左结点，这样等下次pop时就是右节点先打印
（2）偶数层反序，每次奇数层的栈保存偶数层节点，先存右结点，这样等下次pop时就是左节点先打印
class Solution:
def Print(self, pRoot):
# write code here
if pRoot==None:
return []
stack1=[pRoot]
stack2=[]
res1=[]
res2=[]
result=[]
while stack1 or stack2:
res1=[]
res2=[]
# 处理奇数层
while stack1:
node=stack1.pop()
# 按顺序，先存左节点，再存右节点
if node.left:
stack2.append(node.left)
if node.right:
stack2.append(node.right)
res1.append(node.val)
# 收集当前层的结果
if len(res1)!=0:
result.append(res1)
# 处理偶数层
while stack2:
node=stack2.pop()
if node.right:
stack1.append(node.right)
if node.left:
stack1.append(node.left)
res2.append(node.val)
# 收集当前层的结果
if len(res2)!=0:
result.append(res2)
return result
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/99761.html
