2022/06/02

Leetcode Note: Go - Binary Tree Paths

Binary Tree Paths - LeetCode
https://leetcode.com/problems/binary-tree-paths/

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

所感

  • root というバイナリツリーが連携されるので、順不同で全ての root から leaf へのパスを string 配列で return する

回答

[GO] Recursion solution - LeetCode Discuss
https://leetcode.com/problems/binary-tree-paths/discuss/556028/GO-Recursion-solution

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

    paths(root, "", &pathList)

    return pathList
}

func paths(root *TreeNode, prefix string, pathList *[]string) {
    // nil チェック
    if root == nil {
        return
    }

    // prefix チェック
    if len(prefix) == 0 {
        prefix += strconv.Itoa(root.Val)
    } else {
        prefix += "->" + strconv.Itoa(root.Val)
    }

    // child チェック
    if root.Left == nil && root.Right == nil {
        *pathList = append(*pathList, prefix)
        return
    }

    // 再帰
    paths(root.Left, prefix, pathList)
    paths(root.Right, prefix, pathList)
}
  • 再帰で path を探索しつつ文字列を生成していき append で追加していく

See Also