[Golang][Leetcode][BinaryTree]刷題系列-429-N-ary Tree Level Order Traversal

Steven included in Leetcode Golang

2021-08-26 267 words 2 minutes

/leetcode429_binarytree/golang_leetcode.png

Contents

429. N-ary Tree Level Order Traversal

Level : Medium

原題連結 : Click

題目 :

Given an n-ary tree, return the level order traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Example :

Note

Example 1:

Input: root = [1,null,3,2,4,null,5,6] Output: [[1],[3,2,4],[5,6]]

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

解題思路 :

這題是level order traversal的變化題，一樣可以用queue來解決，可以參考 leetcode102題解
從leetcode102題的判斷left children & right children 改成一整個Children array就可以摟!!

Queue解法

if time comlexity of golang built-in function append() is O(1) , time complexity: O(n) , space complexity: O(n)

Runtime: 0 ms, faster than 100.00% of Go online submissions for N-ary Tree Level Order Traversal.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func levelOrder(root *Node) [][]int {
    
    var res [][]int
    
    if root == nil {
        return res
    }
    
    var queue []*Node

    queue = append(queue, root)
    
    for len(queue) != 0 {
        
        length := len(queue)
        
        tempArr := make([]int, 0)

        
        for i := 0; i < length; i++ {
            
            node := queue[0]
            
            
            tempArr = append(tempArr, node.Val)
            
            if len(node.Children) != 0 {
                queue = append(queue, node.Children...)
            }
            
            queue = queue[1:]
            
        }
        
        res = append(res, tempArr)
         
    }
    
    return res
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!