剑指offer刷题笔记59（python）

题目描述

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

思路1

利用两个栈来实现，利用栈先进后出的特点，两个栈分别存储奇数层和偶数层的树节点，如：根节点进入栈1，栈1中的元素依次出栈，没出栈一个元素，就将该元素的子节点压入栈2，要注意栈2的入栈顺序是先左子节点后右子节点（栈先进后出，右子节点后入栈，打印的时候才能先出栈1）。栈2中的元素依次出栈，并将元素的子节点压入栈1中，栈1的入栈顺序是先右子节点后左子节点，这样两个栈依次交替直到两个栈都为空。

代码1

# -*- 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 [] stack1 = [pRoot] stack2 = [] result = [] while (stack1 or stack2): ret1 = [] # 用来暂时存储各层节点的值 ret2 = [] # 用来暂时存储各层节点的值 while stack1: node = stack1.pop() # 先左后右入栈2 if node.left: stack2.append(node.left) if node.right: stack2.append(node.right) ret1.append(node.val) if len(ret1) != 0: result.append(ret1) while stack2: node = stack2.pop() # 先右后左入栈1 if node.right: stack1.append(node.right) if node.left: stack1.append(node.left) ret2.append(node.val) if len(ret2) != 0: result.append(ret2) return result

思路2

判断当前所在层是奇数层还是偶数层，如果是偶数层，就将节点序列reverse。不过这种方法，在数据量特别大的时候效率不高。

代码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 [] rootlist = [pRoot] res = [] n = 1 while rootlist: templist = [] tempres = [] for node in rootlist: tempres.append(node.val) if node.left: templist.append(node.left) if node.right: templist.append(node.right) if n % 2 == 0: tempres.reverse() res.append(tempres) n += 1 rootlist = templist return res