# LeetCode Medium 450. Delete Node in a BST

tags: leetcode

問題

• Explore
• Problems

アイデア

BSTのノードを削除せよという問題です．典型的な問題なのでやるだけ？

解法(recursive)

• rootが空ならrootを返します．
• root.val == keyのとき
  • 右の部分木がなければ，左部分木を返せば良いです．
  • 右の部分木があるとき，右の部分木の最も深い左ノードとrootを交換します．
• 再帰的に，右部分木，左部分木に実行します．

計算量

木のノードの数を$N$，深さを$H$をとします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(H)$

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root: 
            return root
        
        if root.val == key:
            if not root.right:
                return root.left
            else:
                right = root.right
                while right.left:
                    right = right.left
                root.val, right.val = right.val, root.val
            
        root.left = self.deleteNode(root.left, key)
        root.right = self.deleteNode(root.right, key)    
        return root