Tree - 103. Binary Tree Zigzag Level Order Traversal

ppx

2019-08-26

leetcode

103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

return its zigzag level order traversal as:

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

思路：

简单的层序遍历实现题，思想是bfs，只是在输出结果上用做z字序。

代码：

go：

/**

 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    var (
        res [][]int
        level []int
        
        curQ = []*TreeNode{root}
        nextQ []*TreeNode
        reverse = false
    )
    
    if root == nil {
        return res
    }
    
    for len(curQ) != 0 {
        for len(curQ) != 0 {
            var cur *TreeNode
            cur = curQ[0]
            curQ = curQ[1:]

            level = append(level, cur.Val)
            
            if cur.Left != nil {
                nextQ = append(nextQ, cur.Left)
            }
            
            if cur.Right != nil {
                nextQ = append(nextQ, cur.Right)
            }
        }
        if reverse {
            var out []int
            for i := len(level) -1; i >= 0; i-- {
                out = append(out, level[i])
            }
            level = out
        }
        
        res = append(res, level)
        level= nil
        
        curQ = nextQ
        nextQ = nil
        
        if reverse {
            reverse = false
        } else {
            reverse = true
        }
    }
    
    return res
}