スポンサーリンク

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

スポンサーリンク
スポンサーリンク
この記事は約4分で読めます。

 

はじめに

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:

Example 2:

 

Constraints:

  • The number of nodes in the tree is in the range [1, 5000].
  • 1 <= Node.val <= 107
  • root is a binary search tree.
  • 1 <= val <= 107

 

 

内容(和訳)

二分探索木rootがと整数valが与えられます。
二分探索木からvalと同じ値を持つノードとそれ以降の子ノードを含む部分木を返してください。
そのようなノードが存在しない場合はnullを返してください。

 

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

 

解答

 

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

 

幅優先探索での実装。

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

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

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

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

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

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

 

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

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

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

 

 

 

解答2:Python, 再帰

最後の2行では、

・ノードの値がvalよりも小さければ、右の子ノードとvalを引数に自分自身(searchBSTメソッド)を再度呼び出す

・ノードの値がvalよりも大きければ、左の子ノードとvalを引数に自分自身(searchBSTメソッド)を再度呼び出す

 

 

終わりに

補足・参考・感想

 

問題を分類しました。テーマごとに集中して問題を解くことができます。

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

 

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

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

 

 

他の問題もどうぞ

 

前:1448. Count Good Nodes in Binary Tree

 

次:450. Delete Node in a BST

 

LeetCode 解答・解説記事一覧

 

コメント