【LeetCode】700. Search in a Binary Search Tree 解答・解説【Python】

はじめに
1. ポイント
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python,幅優先探索(BFS)
  2. 解答2：Python, 再帰
終わりに
1. 補足・参考・感想
2. 他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

これまでこのサイトでメモしてきた問題はこのページに全て載せています。

LeetCode 解答・解説記事一覧

二分探索、連結リストなど、テーマを絞って集中的に解きたい方は以下の記事が有用です。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

- 二分探索木の性質
- BFS
- 再帰

詳細

問題

原文

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Example 1:

Input: root = [4,2,7,1,3], val = 2 Output: [2,1,3]

1
2

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Example 2:

Input: root = [4,2,7,1,3], val = 5 Output: []

1
2

Input: root = [4,2,7,1,3], val = 5
Output: []

Constraints:

The number of nodes in the tree is in the range [1, 5000].

1 <= Node.val <= 10⁷

root is a binary search tree.

1 <= val <= 10⁷

内容(和訳)

二分探索木rootがと整数valが与えられます。

二分探索木からvalと同じ値を持つノードとそれ以降の子ノードを含む部分木を返してください。

そのようなノードが存在しない場合はnullを返してください。

※正しくない可能性があります。

解答

解答1：Python,幅優先探索(BFS)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root: return root
        
        q = deque()
        q.append(root)
        
        while q:
            node = q.popleft()
            if node.val == val: return node
            elif node.val < val and node.right: q.append(node.right)
            elif node.val > val and node.left: q.append(node.left)
        
        return None

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:

if not root: return root

q = deque()

q.append(root)

while q:

node = q.popleft()

if node.val == val: return node

elif node.val < val and node.right: q.append(node.right)

elif node.val > val and node.left: q.append(node.left)

return None

幅優先探索での実装。

while文の中では以下の処理を行う。

・ノードをキューから取り出す

・ノードの値がvalと一致したらそのノードを返す。

※返されるノードには子孫のノードが含まれており、これ自体が解答として求められている部分木になっている。

・ノードの値がvalよりも小さく、右の子ノードがあればキューに追加

・ノードの値がvalよりも大きく、左の子ノードがあればキューに追加

幅優先探索といっても、ある階層の全てのノードをキューに入れて処理を行う必要はない。

二分探索木の各ノードの値はは、左の子＜=親＜=右の子となっているので、

親ノードの値と、valを比較したときに、valが含まれている方の部分木だけをキューに追加する。

解答2：Python, 再帰

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root: return None
        if root.val == val: return root
        if root.val < val: return self.searchBST(root.right, val)
        if root.val > val: return self.searchBST(root.left, val)