##递归法
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val)
#向左遍历
if val > root.val:
root.right = self.insertIntoBST(root.right,val) #1
#向右遍历
elif val < root.val:
root.left = self.insertIntoBST(root.left,val) #2
return root235. 二叉搜索树的最近公共祖先
文档讲解：代码随想录
题目链接：. - 力扣（LeetCode）
提到二叉搜索树，那么我们就要好好利用它的特性
p和q的公共祖先一定是在p和q的中间的（如果一个节点在p和q之间，那么说明p在这个节点的左子树，q在这个节点的右子树中），所以：
p和q的最近公共祖先一定是小于等于p和q的中的最大值，大于等于p和q中的最小值的
所以当前遍历的节点如果在这个范围的右边，那么我们就向左遍历，反之向右遍历
是否一定是最近的公共祖先呢？假设现在找到了一个公共节点，如果我们再向左或者右遍历，那么就会错过p或者q。所以找到的一定是最近的公共祖先
递归法
递归的三要素：
第一要素：明确这个函数想要干什么
传入一个节点，找到这个节点对应的二叉树中p和q的最近公共祖先
第二要素：寻找递归结束条件
如果传入的是空那么就return 空
如果传入的节点的值就在p和q之间，那么就return 这个节点
第三要素：找出函数的等价关系式
如果当前遍历的节点如果在这个范围的右边，那么我们就继续向左遍历，反之向右遍历
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
##终止条件
if not root:
return None
if root.val>min(p.val,q.val) and root.val < max(p.val,q.val):
return root
##递归遍历
if root.val < min(p.val,q.val):
return self.lowestCommonAncestor(root.right,p,q)
elif root.val > max(p.val,q.val):
return self.lowestCommonAncestor(root.left,p,q)
else:
return root迭代法
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
##终止条件
if not root:
return None
while root:
if root.val < min(p.val,q.val):
root = root.right
elif root.val > max(p.val,q.val):
root = root.left
else:
return root701.二叉搜索树中的插入操作
文档讲解：代码随想录
题目链接：. - 力扣（LeetCode）
有多种插入方式，我们选择直接在叶子节点插入
要点：在二叉搜索树中，插入任何一个节点，都可以在叶子节点找到它的位置。主要是要比较要插入的节点与当前遍历到的节点的大小，决定我们是向左还是向右遍历，直到遇到空节点，将数值插入即可，保证二叉搜索树的特性不变。
递归法
迭代法
##迭代法
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val)
current = root
while current: ##不可以用root循环，因为会不变改变root，最后还要返回root
#向左遍历
if val > current.val:
if current.right == None:
current.right = TreeNode(val)
break
current= current.right
#向右遍历
elif val < current.val:
if current.left == None:
current.left = TreeNode(val)
break
current= current.left
return root450.删除二叉搜索树中的节点
文档讲解：代码随想录
题目链接：. - 力扣（LeetCode）
与上题相比添加节点只要在叶子节点添加即可，但是删除二叉树的节点需要改变二叉树的结构，比上题难得多。分五种情况
①没有找到删除的节点
②要删除的节点是叶子节点：不用改变二叉树的结构，较简单
③要删除的节点左不为空，右为空
④要删除的节点左为空，右不为空
⑤左右都不空。假设我们让右子树即位，那么原来左子树就要寻找一个新的父节点，只需要找比原来父节点稍微大一点的数即可。即右子树中最左侧的节点，这样就比左子树稍微大一点点。
递归的三要素：
第一要素：明确这个函数想要干什么
传入一个节点，删除以这个节点为根节点的二叉树中的特定值，并返回删除后的二叉树（根节点）
第二要素：寻找递归结束条件
上面说到的5点
第三要素：找出函数的等价关系式
根据特定的搜索方向删除左子树或者右子树中的值，删除完之后不要忘记，让根节点指向它们，因为根节点还在的，我们只是修改了根节点的左子树或者右子树，删完之后要更新一下
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
#如果是空
if not root:
return None
#如果当前节点是要删除的节点
if root.val == key:
#如果要删除的节点是叶子节点
if not root.left and not root.right:
return None
#左不为空，右为空
if root.left and not root.right:
return root.left
#左为空，右不为空
if not root.left and root.right:
return root.right
if root.left and root.right:
cur = root.right
##找到右子树最左边的节点
while cur.left:
cur = cur.left
cur.left = root.left
##相当于左孩子为空了，直接返回右孩子即可
return root.right
#递归，二叉搜索树决定了搜索的方向
else:
if key > root.val:
node = self.deleteNode(root.right,key)
root.right = node
return root
else:
node = self.deleteNode(root.left,key)
root.left = node
return root这几道题目的递归函数都是有返回值的，并且让上一个节点的左孩子或者右孩子接住了，之后还是要好好消化消化
