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/

Approach 1: Recursive Approach
- Node を再帰的にチェックしていく
Approach 2: Iterating method using Stack
- 再帰ではなく Stack を使って Node をチェックしていく
Approach 3: Morris Traversal
- https://www.educative.io/edpresso/what-is-morris-traversal
- https://en.wikipedia.org/wiki/Tree_traversal

回答

/**
 * 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 する配列に追加していく
実装した再帰関数を呼び出す