2022/09/01

Leetcode Note: Go - Search in a Binary Search Tree

Search in a Binary Search Tree - LeetCode
https://leetcode.com/problems/search-in-a-binary-search-tree/

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

所感

  • BST: Binary Search Tree と int の値 val が渡される
  • val の値を持つ Node と、その子孫の値を int 配列で return する

回答

100% golang solution - LeetCode Discuss
https://leetcode.com/problems/search-in-a-binary-search-tree/discuss/263927/100-golang-solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
    if root==nil {
        return nil
    }

    if val==root.Val {
        return root
    } else if val > root.Val {
        return searchBST(root.Right,val)
    } 
    return searchBST(root.Left,val)
}
  • nil チェック
  • root.Val が val と一致するなら root を return
  • root.Val が val より小さい場合は root.Right を対象に再帰
  • それ以外の場合は root.Left を対象に再帰
  • BST は左右で大きさを判定できるので val との大小比較で対象をフィルタしていくことが有効

See Also