スポンサーリンク

【LeetCode】450. Delete Node in a BST 解答・解説【Python】

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

 

 

はじめに

LeetCodeの問題を解答します。

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

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

 

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

LeetCode 解答・解説記事一覧

 

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

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

 

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

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

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

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

 

 

ポイント

    • 二分探索木の検索
    • ノード削除後の二分探索木の維持

 

 

詳細

 

問題

 

原文

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

  1. Search for a node to remove.
  2. If the node is found, delete the node.

 

Example 1:

Example 2:

Example 3:

 

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -105 <= Node.val <= 105
  • Each node has a unique value.
  • root is a valid binary search tree.
  • -105 <= key <= 105

 

Follow up: Could you solve it with time complexity O(height of tree)?

 

 

内容(和訳)

与えられたBST(二分探索木)のルートノード参照とキーに基づいて、BST内の指定されたキーを持つノードを削除します。BSTのルートノード参照(必要に応じて更新される可能性があります)を返します。

基本的に、削除は次の2つのステージに分けることができます:

1. 削除するノードを検索します。
2. ノードが見つかった場合、ノードを削除します。

 

※ChatCPTによる翻訳

 

解答

 

解答1:Python, 再帰

 

 

 

終わりに

補足・参考・感想

 

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

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

 

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

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

 

 

他の問題もどうぞ

 

前:700. Search in a Binary Search Tree

 

次:841. Keys and Rooms

 

LeetCode 解答・解説記事一覧

 

コメント