はじめに
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:
- Search for a node to remove.
- If the node is found, delete the node.
Example 1:
123456 Input: root = [5,3,6,2,4,null,7], key = 3Output: [5,4,6,2,null,null,7]Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.One valid answer is [5,4,6,2,null,null,7], shown in the above BST.Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.<img src="https://assets.leetcode.com/uploads/2020/09/04/del_node_supp.jpg" alt="" />Example 2:
123 Input: root = [5,3,6,2,4,null,7], key = 0Output: [5,3,6,2,4,null,7]Explanation: The tree does not contain a node with value = 0.Example 3:
12 Input: root = [], key = 0Output: []
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, 再帰
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
# 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 deleteNode(self, root: TreeNode, key: int) -> TreeNode: #ノードがなければNoneを返す if not root: return None #ノードの値がkeyよりも小さい場合、自身を再度呼び出して右の子ノードに入れる if key > root.val: root.right = self.deleteNode(root.right, key) #ノードの値がkeyよりも大きい場合、自身を再度呼び出して左の子ノードに入れる elif key < root.val: root.left = self.deleteNode(root.left, key) #ノードの値がkeyと一致した場合 else: #左右の子ノードがない、つまり葉ノードの場合はNoneを返す if not root.left and not root.right: root = None #右の子ノードがある場合 elif root.right: #右の子ノードがある場合、successorメソッドを呼び出す。 #successorは、右の子ノードを親とする木の中で、最小値(一番左のノード)のノードの値を保持する root.val = self.successor(root) #右の子ノードには、右の子ノードを親ノード、keyとしてdeleteNodeを呼び出す root.right = self.deleteNode(root.right, root.val) #左の子ノードがある場合、predecessorメソッドを呼び出す。 elif root.left: #predecessorは、左の子ノードを親とする木の中で、最大値(一番右のノード)のノードの値を保持する root.val = self.predecessor(root) #左の子ノードに、deleteNodeの結果を入れる root.left =self.deleteNode(root.left, root.val) return root #補助メソッド。削除対象のノードが見つかった時、削除対象と入れ替わる新たな親ノードを探す。 #右の子ノードがある場合は、右の子ノードを親とする木の最小値(一番左の葉ノード)を、削除対象と入れ替える def successor(self, root: TreeNode) -> TreeNode: root = root.right while root.left: root = root.left return root.val #補助メソッド。削除対象のノードが見つかった時、削除対象と入れ替わる新たな親ノードを探す。 #左の子ノードがある場合は、左の子ノードを親とする木の最大値(一番右の葉ノード)を、削除対象と入れ替える def predecessor(self, root: TreeNode) -> TreeNode: root = root.left while root.right: root = root.right return root.val |
終わりに
補足・参考・感想
問題を分類しました。テーマごとに集中して問題を解くことができます。
LeeetCodeの問題をアルゴリズムとデータ構造による分類
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。
他の問題もどうぞ
前:700. Search in a Binary Search Tree
コメント