2022/04/17

Leetcode Note: Go - Binary Tree Inorder Traversal

Binary Tree Inorder Traversal - LeetCode
https://leetcode.com/problems/binary-tree-inorder-traversal/

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

所感

  • バイナリツリーの root が与えられた時に、そのノードの値を順方向へのトラバースを返す
  • Inorder => 順方向
  • Traversal => 漏れなく辿って要素を返す
  • バイナリツリーが持っている要素の null をチェックしつつ int 配列を生成すれば実装できそうかも？

実装準備

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    
}

Solution

Binary Tree Inorder Traversal - LeetCode
https://leetcode.com/problems/binary-tree-inorder-traversal/solution/

回答

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    traversal := []int{}
    
    var inorder func(*TreeNode) 
    
    inorder = func(root *TreeNode) {
        if root == nil {
            return
        }
        
        inorder(root.Left)
        traversal = append(traversal, root.Val)
        inorder(root.Right)
    }
    inorder(root)
    
    return traversal;
}
  • return する配列を定義
  • 再帰関数を定義、実装
    • 引数で受け取った TreeNode が nil なら return
    • Left からチェックして Val を return する配列に追加していく
  • 実装した再帰関数を呼び出す

See Also