LeetCode103——二叉树的锯齿形层序遍历

2022年2月6日 · 149 字 · 1 分钟

题目

给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

示例 1:

img

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[20,9],[15,7]]

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

用层序遍历的思路即可,不过偶数行需要将该行的值翻转。

// BFS处理,记录遍历层数,当层数是奇数,翻转下本层元素
func zigzagLevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	answers := [][]int{}
	queue := []*TreeNode{root}
	for level := 1; len(queue) > 0; level++ {
		size := len(queue)
		tmp := queue
		queue = []*TreeNode{} // 清空,存储下一层的节点
		vals := []int{}
		for i := 0; i < size; i++ {
			node := tmp[0]
			tmp = tmp[1:]
			vals = append(vals, node.Val)
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		if level%2 == 0 { // 偶数行,翻转vals
			length := len(vals)
			for i := 0; i < length/2; i++ {
				vals[i], vals[length-1-i] = vals[length-1-i], vals[i] // length-1是结束下标,-i就是同步往左逼近
			}
		}
		answers = append(answers, vals)
	}
	return answers
}