Leetcode - sort-list
Leetcode - Permutations && Permutations-ii

Leetcode - binary-tree-zigzag-level-order-traversal

violet posted @ Mar 14, 2020 02:23:37 AM in 胡扯 with tags Algorithm Golang BFS , 342 阅读

https://leetcode.com/problems/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],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

 

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    queue := []*TreeNode{root}
    result := [][]int{}
    level := 0
    for len(queue) != 0 {
        size := len(queue)
        levelResult := []int{}
        for i := 0; i < size; i++ {
            node := queue[i]
            levelResult = append(levelResult, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        level++
        if level%2 == 0 {
            levelResult = reverse(levelResult)
        }
        result = append(result, levelResult)
        queue = queue[size:]
    }
    return result
}

func reverse(nums []int) []int {
    size := len(nums)
    for i := 0; i < size/2; i++ {
        nums[i], nums[size-1-i] = nums[size-1-i], nums[i]
    }
    return nums
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter