77.md

按之字形顺序打印二叉树

题目

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

要求：空间复杂度：O(n)，时间复杂度：O(n)

示例

输入：{1,2,3,#,#,4,5}

返回值：[[1],[3,2],[4,5]]

说明：如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。

思路

• 从根节点开始，将左右子节点装入数组待下一轮处理
• 因为要之字形打印所以要记录方向，每轮反转

实现

func Print(pRoot *TreeNode) [][]int {
	if pRoot == nil {
		return nil
	}
	nodeToBeMachined := []*TreeNode{pRoot} // 待处理的一层节点
	result := [][]int{{pRoot.Val}}
	reverse := true // 方向标识
	for len(nodeToBeMachined) != 0 {
		nextLevelNodes := make([]*TreeNode, 0)
		row := make([]int, 0)
		for _, item := range nodeToBeMachined {
			// 待处理节点始终是从左向右的
			if item.Left != nil {
				nextLevelNodes = append(nextLevelNodes, item.Left)
				row = append(row, item.Left.Val)
			}
			if item.Right != nil {
				nextLevelNodes = append(nextLevelNodes, item.Right)
				row = append(row, item.Right.Val)
			}
		}
		nodeToBeMachined = nextLevelNodes
		length := len(row)
		if length != 0 {
			if reverse {
				for i := 0; i < length/2; i++ {
					row[length-1-i], row[i] = row[i], row[length-1-i]
				}
			}
			result = append(result, row)
		}
		reverse = !reverse // 转向
	}
	return result
}