当前位置:网站首页>Leetcode 450. Deleting a node in a binary search tree
Leetcode 450. Deleting a node in a binary search tree
2022-06-11 16:42:00 【von Libniz】
link :https://leetcode.cn/problems/delete-node-in-a-bst/
The addition, deletion, modification and query of binary search tree are necessary contents , But deleting is a little more difficult than other operations , You can practice with this question .
Title Description
Given the root node of a binary search tree root And a value key, Delete the key Corresponding node , And keep the property of binary search tree unchanged . Back to binary search tree ( May be updated ) Reference to the root node of .
The recursive method
class Solution:
""" The recursive method """
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
""" Delete root as root Of BST in node.val be equal to key The node of , Returns the deleted root node ( Root node may change ) """
if not root:
return None
if key < root.val:
root.left = self.deleteNode(root.left, key)
elif root.val < key:
root.right = self.deleteNode(root.right, key)
# # root There may be 0 or 1 A child node , But the treatment is the same , Return to the child node
elif not root.left or not root.right:
child = root.left if root.left else root.right
return child
else:
successor = root.right # Use successor nodes instead of root
while successor.left:
successor = successor.left
root.val = successor.val # root.val Assign values to subsequent nodes
root.right = self.deleteNode(root.right, successor.val)
return root
Iterative method
The basic idea of iterative solution is the same as above , This is to discuss whether the deleted node is the root node in multiple categories .
class Solution:
""" Non recursive solution """
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return root
node, father = self.findNode(root, key)
if not node:
return root
return self.delete(root, father, node)
def delete(self, root, father, node):
if node.left and node.right:
suc_father, successor = self.findSuccessor(node)
node.val = successor.val
return self.delete(root, suc_father, successor)
if not node.left and not node.right:
if root == node:
return None
if father.left == node:
father.left = None
else:
father.right = None
return root
child = node.left if node.left else node.right
if root == node:
return child
if father.left == node:
father.left = child
else:
father.right = child
return root
def findNode(self, root, key):
if not root:
return root
if root.val == key:
return root, None
father = root
while root:
if root.val == key:
return root, father
elif key < root.val:
father = root
root = root.left
else:
father = root
root = root.right
return None, None
def findSuccessor(self, root):
successor = root.right
father = root
while successor.left:
father = successor
successor = successor.left
return father, successor
边栏推荐
- 核密度估计(二维、三维)
- RDKit 安装
- 2022年危险化学品经营单位主要负责人考试模拟100题及模拟考试
- If you want to learn ArrayList well, it is enough to read this article
- tornado环境搭建及基本框架搭建——熟悉的hello world
- Pytest test framework Basics
- 数据库备份(Mysql)
- 2022 high voltage electrician special operation certificate examination question bank and online simulation examination
- SQL injection attack under seed emulator (including SQL environment configuration)
- Pyqt5 enables the qplaintextedit control to support line number display
猜你喜欢

Switching power supply circuit diagram and principle 12V analysis - detailed version

Pytest test framework Basics

GemBox.Bundle 43.0 Crack

Opencv相机标定之圆形标识点中心检测

Katalon Studio Enterprise

Global and Chinese molten carbonate fuel cell industry outlook and market panoramic Research Report 2022-2028

Leetcode 1974. Minimum time to type words using a special typewriter (yes, once)

Kernel density estimation (2D, 3D)

1267_ FreeRTOS starts the first task interface prvportstartfirsttask implementation analysis

2022年安全员-B证国家题库及模拟考试
随机推荐
【pytest学习】pytest 用例执行失败后其他不再执行
Learn about Prometheus from 0 to 1
Rdkit tutorial
Pytest测试框架基础篇
Pytest test framework Basics
如何把树结构存储到数据库
^31原型面试题
web安全-靶场笔记
Exception handling and exception usage in golang
2022起重机司机(限桥式起重机)考试题模拟考试题库及模拟考试
2022 molten welding and thermal cutting work license and simulation examination
2022安全员-A证考试题模拟考试题库模拟考试平台操作
The flat life of older farmers from Beijing to Holland
Ruiji takeout project (III) employee management business development
[learn FPGA programming from scratch -18]: quick start chapter - operation steps 2-6- VerilogHDL sequential circuit syntax analysis (taking the counter as an example)
solr(一)solr的安装及权限控制
Elasitcsearch basic learning notes (1)
7个人生工具:SWOT、PDCA、6W2H、SMART、WBS、时间管理、二八原则
2022 R1 quick opening pressure vessel operation test question bank and simulation test
leetcode684. Redundant connection (medium)