2022/08/06

Leetcode Note: Go - N-Ary Tree Postorder Traversal

N-ary Tree Postorder Traversal - LeetCode
https://leetcode.com/problems/n-ary-tree-postorder-traversal/

  • Go 言語で取り組んだメモ

所感

  • linked list の nodeを post order traversal して int 配列で return する
    • node の末端から value を集めていく

回答

Go: Iterative solution (using list) - LeetCode Discuss https://leetcode.com/problems/n-ary-tree-postorder-traversal/discuss/549341/Go%3A-Iterative-solution-(using-list)

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func postorder(root *Node) []int {
    res := []int{}
    if root == nil {
        return res
    }
    
    stack := list.New()
    stack.PushFront(root)
    for stack.Len() > 0 {
        curr := stack.Remove(stack.Front()).(*Node)
        if curr != nil {
            res = append(res, curr.Val)        
        }
    
        for i := 0; i < len(curr.Children) ; i++ {
            stack.PushFront(curr.Children[i])
        }
    }
    
    reverse(res)
    
    return res
}

func reverse (s []int) {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}
  • golang では container/list パッケージで提供されている list が stack として使える
  • stack に root node を格納
  • node が存在する間ループを行い、走査した value を res に push していき return 直前で反転する

See Also