LeetCode 103 二叉树Z字形层次遍历

1 题目描述

给定一个二叉树，返回其值的Z字形层次遍历。（如，先从左到右，下一层从右到左，以此类推，直至最后一层遍历完成）

例子：

输入：

[3,9,20,null,null,15,7]

输出：

[[3], [20,9], [15,7]]

题目出处：LeetCode

2 解决思路

将根节点设为第0层，采用迭代算法，每一次遍历一层，针对每层的遍历，判断该层是奇数层还是偶数层，偶数层正序追加节点，奇数层逆序追加节点。遍历完成即得到结果。

3 Golang实现代码

https://github.com/leileiluoluo/

func zigzagLevelOrder(root *TreeNode) [][]int {
	if nil == root {
		return [][]int{}
	}

	var allVals [][]int
	nodes := []*TreeNode{root}
	level := 0
	for len(nodes) > 0 {
		var vals []int
		tmp := nodes[:]
		nodes = []*TreeNode{}
		for _, p := range tmp {
			if 0 == level%2 {
				vals = append(vals, p.Val)
			} else {
				vals = append([]int{p.Val}, vals...)
			}
			if nil != p.Left {
				nodes = append(nodes, p.Left)
			}
			if nil != p.Right {
				nodes = append(nodes, p.Right)
			}
		}
		allVals = append(allVals, vals)
		level++
	}
	return allVals
}

LeetCode 103 二叉树Z字形层次遍历

相关文章

评论