LeetCode 235. 二叉搜索树的最近公共祖先
思路：
- 根据二叉搜索树的特性，对 “基于二叉树的最近公共祖先 ” 进行优化，在二叉树寻找最近公共祖先时，需要分别对根节点的两个子树进行遍历来判断两个节点是异侧还是同侧。
- 但是在二叉搜索树中，小于根节点的一定是在左子树，大于根节点的一定是在右子树。我们可以根据这个特性，先判断两个节点的值，如果一个大于根节点的值，一个小于根节点的值，那么左右子树都需要进行遍历。如果都大于/都小于，那就只遍历一边就行了，另外一边就可以起到不进行遍历的作用。从上往下遍历时，找到符合条件的即为最近公共祖先。
手撕Code：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
### 不同于在二叉树的最近公共祖先，如何利用二叉搜索树的特性进行优化
result = self.inorder_Search(root, p, q)
return result
def inorder_Search(self, root, p, q):
if not root: ## 到最底部
return None
left_tree = self.inorder_Search(root.left, p, q)
if root.val == p.val or root.val == q.val: ### 找到了节点
return root
right_tree = self.inorder_Search(root.right, p, q)
if root.val > p.val and root.val < q.val: ## 分布在处理节点左右两边
return root
if root.val < p.val and root.val > q.val: ## 分布在处理节点左右两边
return root
if root.val > p.val and root.val > q.val: ### 分布在处理节点同一侧
return left_tree
if root.val < p.val and root.val < q.val:
return right_tree优化：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
### 不同于在二叉树的最近公共祖先，如何利用二叉搜索树的特性进行优化
result = self.inorder_Search(root, p, q)
return result
def inorder_Search(self, root, p, q):
if not root: ## 到最底部
return None
if root.val > p.val and root.val > q.val: ### 分布在处理节点同一侧
left_tree = self.inorder_Search(root.left, p, q)
if left_tree:
return left_tree
if root.val < p.val and root.val < q.val:
right_tree = self.inorder_Search(root.right, p, q)
if right_tree:
return right_tree
return root注意：
- if not left == if left is None, if left == if left is not None
LeetCode 701.二叉搜索树中的插入操作
思路：
- 在保留原有二叉搜索树形状的基础上进行插入操作。具体地，根据二叉搜索树的特性进行遍历，当遍历到符合二叉搜索树插入节点的父节点时，判断该父节点下有无位置可以进行插入，有的话则直接进行插入操作。在这个过程需要通过一个全局变量pre来记录上一个操作节点的指针，以方便后续进行插入操作。
- 总结：不更改原有树的结构，在符合二叉搜索树的前提下，若有空叶子节点位置可以插入就直接插入。
- 存在的问题是：如何多次插入更多会导致树出现不平衡，但题目没要求，可以不用管，需要注意到有这个现象就行。
手撕Code：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def insertIntoBST(self, root, val):
"""
:type root: Optional[TreeNode]
:type val: int
:rtype: Optional[TreeNode]
"""
### 思路1：中序遍历一边原二叉搜索树，得到数组。随后基于数组去插入对应的节点值，得到新的二叉搜索树的数组，再基于这个数组来构造新的二叉搜索树
### 思路2：根据二叉搜索树的遍历方式，直接往空节点进行插入即可，如示例1的方式
self.pre = None ### 记录上一个节点指针
val = TreeNode(val=val)
if not root:
root = val
else:
self.search(root, self.pre, val)
return root
def search(self, root, pre, val):
if not root:
if self.pre.val < val.val:
self.pre.right = val
if self.pre.val > val.val:
self.pre.left = val
else:
self.pre = root
if val.val < root.val:
self.search(root.left, self.pre, val)
if val.val > root.val:
self.search(root.right, self.pre, val)LeetCode 450.删除二叉搜索树中的节点
思路：
- 根据删除结点的位置进行对应的逻辑操作，并用一个pre指针来指向要删除节点的父节点。
首先，删除节点的类型有四种：
- 删除节点是叶子节点，那么直接进行删除即可
- 删除节点有左子树，无右子树（左不空，右空）。那么需要该删除节点的父节点需要继承删除节点的左子树
- 删除节点有右子树，无左子树（右不空，左空）。那么需要该删除节点的父节点需要继承删除节点的右子树
- 删除节点都左右子树，那么需要对这两个子树进行整合，构成一颗新的二叉搜索子树，添加到删除节点的父节点之下。两种实现方式，第一种是将删除节点的右子节点连接到删除节点的父节点，并将其左子树继承到该右子树的最左下部分。第二种是删除节点的左叶子节点连接到删除节点的父节点，并将其右子树继承到该左子树的最右下部分。代码采用的是第一种重构。
手撕Code：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def deleteNode(self, root, key):
"""
:type root: Optional[TreeNode]
:type key: int
:rtype: Optional[TreeNode]
"""
### 情况1：如果是叶子节点，直接删除
### 情况2：如果是父节点，则需要对其下的子树进行重构。由于左中右是单调有序，因此重构操作只需要将右子节点往左旋转成为新的父节点即可
if not root: ##空树
return None
self.pre = None ### 记录删除父节点的指针
result = self.search(root, self.pre, key)
return result
def search(self, root, pre, key):
### 终止条件
if not root: ## 删除节点在树中不存在
return None
# print("self.pre", self.pre)
# print("root", root)
if key < root.val:
self.pre = root
self.search(root.left, self.pre, key)
if key > root.val:
self.pre = root
self.search(root.right, self.pre, key)
if root.val == key: ### 找到了删除节点
if root and not self.pre: ### 删除根节点
if not root.left and not root.right: ### 左空, 右空
root = None
elif not root.left and root.right: ### 左空, 右不空
root = root.right
elif root.left and not root.right: ### 左不空, 右空
root = root.left
elif root.left and root.right: ### 左不空, 右不空
temp = root.left
root = root.right
cur = root
while cur:
add_node = cur
cur = cur.left
add_node.left = temp
else:
if not root.left and not root.right: ### 左空, 右空
if self.pre.left == root:
self.pre.left = None
if self.pre.right == root:
self.pre.right = None
if not root.left and root.right: ### 左空, 右不空
if self.pre.left == root:
self.pre.left = root.right
if self.pre.right == root:
self.pre.right = root.right
if root.left and not root.right: ### 左不空, 右空
if self.pre.left == root:
self.pre.left = root.left
if self.pre.right == root:
self.pre.right = root.left
if root.left and root.right: ### 左不空, 右不空
if self.pre.left == root: ### 删除节点在左子树
self.pre.left = root.right
if self.pre.right == root: ### 删除节点在右子树
self.pre.right = root.right
cur = root.right
while cur :
add_node = cur
cur = cur.left
add_node.left = root.left
return root代码缺陷：
- 采用双指针来进行删除操作，但对于删除节点为根节点时需要额外进行判断，代码不能统一。
- 另外，在进行继承操作时，还需要判断删除节点在父节点的哪边，因此代码出现了较多的if判断。
代码优化思路：
- 修改包括删除节点下对应的子树，并将对应的子树的根节点进行返回即可，后续要进行继承操作，只需要继承这个子树的根节点。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def deleteNode(self, root, key):
"""
:type root: Optional[TreeNode]
:type key: int
:rtype: Optional[TreeNode]
"""
if not root: ## 如果在树中找不到这个满足条件的节点
return root ## 返回原来的树
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 ### 重构完后返回当前重构子树的根节点
### root 为删除节点的父节点
if key < root.val: ### 遍历
root.left = self.deleteNode(root.left, key) ### 将修改完的左子树赋予根节点的left指针
if key > root.val:
root.right = self.deleteNode(root.right, key)### 将修改完的右子树赋予根节点的right指针
return root