代码随想录算法训练营day19| 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点

学习资料：https://programmercarl.com/0235.二叉搜索树的最近公共祖先.html****

学习记录：
235.二叉搜索树的最近公共祖先（加一个函数traversal）

点击查看代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def traversal(self, cur, p, q):if cur is None:return curif cur.val > p.val and cur.val > q.val:left = self.traversal(cur.left, p, q)if left is not None:return leftif cur.val < p.val and cur.val < q.val:right = self.traversal(cur.right, p, q)if right is not None:return rightreturn curdef lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""return self.traversal(root, p, q)

701.二叉搜索树中的插入操作（递归法，返回root；根据左<根<右的规则，先左再右子树的遍历）

点击查看代码

# 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]"""if not root:node = TreeNode(val)return nodeif root.val > val:root.left = self.insertIntoBST(root.left, val)if root.val < val:root.right = self.insertIntoBST(root.right, val)return root

450.删除二叉搜索树中的节点（情况很多，要仔细考虑；用返回值来代替删除过程；删除根节点、删除左子树上的节点、或者删除右子树上的节点，后两种直接递归）

点击查看代码

# 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]"""# 如果root为空，就返回rootif root is None:return root# 删除根节点的4种情况：都是通过返回值的形式达到删除节点的目的if root.val == key:# 1：二叉树就一个根节点，那就返回空if not root.left and not root.right:return None# 2：根节点只有右子树，就返回右子树elif not root.left:return root.right# 3：根节点只有左子树，就返回左子树elif not root.right:return root.left# 4：根节点有左和右子树，因为满足左<根<右的条件，在右子树的某个左节点（该左节点没有左子树）下接左子树。else:cur = root.rightwhile cur.left is not None:cur = cur.leftcur.left = root.leftreturn root.right# 当待删除的节点非根节点时，用递归法if root.val < key:root.right = self.deleteNode(root.right, key)if root.val > key:root.left = self.deleteNode(root.left, key)return root

PS:今天有点疲惫了，简单学了一遍，也没听太懂，比较喜欢添加和删除节点这种题。
今天吃了猪肘饭，不合胃口，配菜倒挺香
马上迎来周末了！脑子都快装不下了 哈哈哈