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

写在前边的话

235. 二叉搜索树的最近公共祖先

题目链接

        力扣题目链接

题目难度

        中等

看到题目的第一想法

        看到题目的第一想法，除了昨天做过的普通二叉树的最近祖先的解法利用回溯从底向上搜索，我会想到使用迭代法，但我好像不太会使用到二叉树搜索树的特性，我是选择的层序遍历。得转换下思维了。

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if not root:return rootqueue = collections.deque([root])while queue:n = len(queue)for i in range(n):node = queue.popleft()if min(p.val, q.val) <= node.val <= max(p.val, q.val):return nodeif node.left:queue.append(node.left)if node.right:queue.append(node.right)return None

       

看完代码随想录的总结

文章讲解

        代码随想录文章讲解

视频讲解

        代码随想录视频讲解

解题思路

        1. 递归法：由于没有中节点的逻辑所以前中后序都是可以的。

           递归三步曲：

           1）入参：根节点，p，q；返回值：满足条件的二叉树节点。

           2）终止条件：节点空返回空

           3）单次递归逻辑：如果节点小于p，q那么就向右子树遍历；如果节点值大 于p，q那么就向左子树遍历；否则就返回当前节点。

        2. 迭代法

            从根节点开始遍历，如果当前节点小于p，q那么就向右子树搜索；如果当前节点值大于p，q那么就像左子树搜索；否则返回当前节点。

代码编写

python

# 递归法
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if not root:return rootprint(root.val)if root.val < p.val and root.val < q.val:right_res = self.lowestCommonAncestor(root.right, p, q)if right_res:return right_resif root.val > p.val and root.val > q.val:left_res = self.lowestCommonAncestor(root.left, p, q)if left_res:return left_resreturn root#********************************************************************************# 迭代法
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':cur = rootwhile cur:if cur.val < p.val and cur.val < q.val:cur = cur.rightelif cur.val > p.val and cur.val > q.val:cur = cur.leftelse:return curreturn None

java

701.二叉搜索树中的插入操作

题目链接

        力扣题目链接

题目难度

        中等

看到题目的第一想法

        看到题目的第一想法是想用迭代法，在遍历节点的时候找到要插入的位置。

        python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:node = TreeNode(val)if not root:return nodecur = rootwhile True:if val < cur.val:print(cur.val)if not cur.left:   cur.left = nodereturn rootelse:cur = cur.leftif val > cur.val:if not cur.right:node = TreeNode(val)cur.right = nodereturn rootelse:cur = cur.right

看完代码随想录的总结

文章讲解

        代码随想录文章讲解

视频讲解

        代码随想录视频讲解

解题思路

        1.递归法：需要记录父节点（方案一：可以通过递归函数的返回值完成父子节点的赋值这种方法比较便利，方案二：另外也可以找到要插入父节点位置以后再判断是插入到左节点还是右节点）

          递归三步曲方案一：

          入参：当前节点以及要比较的数值，返回值要插入的节点。

          终止条件：节点空则返回要插入的节点。

          单次递归逻辑：赋值当前节点给父节点；如果节点值大于要比较的值，那么向左子树遍历；如果当前节点值小于要比较的值，那么向右子树遍历。注意这里返回值会赋值给左右子节点。

           递归三步曲方案二：

          入参：当前节点以及要比较的数值，无返回值。

          终止条件：节点空即下层左节点或者右节点为空了，这个时候由于递归函数没有返回值，所以需要检查比较值是大于父节点还是小于父节点，小于插入到左节点，大于插入到右节点。

          单次递归逻辑：赋值当前节点给父节点；如果节点值大于要比较的值，那么向左子树遍历；如果当前节点值小于要比较的值，那么向右子树遍历。

代码编写

python

#方案一
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def __init__(self):self.parent  = Nonedef reversal(self, cur, val):if not cur:node = TreeNode(val)return nodeif cur.val > val:cur.left = self.reversal(cur.left, val)else:cur.right = self.reversal(cur.right, val)return cur  # 注意这里要一层一层返回最终返回的就是根节点了def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if not root:return TreeNode(val)cur = rootreturn self.reversal(cur, val)#********************************************************************# 方案二
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def __init__(self):self.parent  = Nonedef reversal(self, cur, val):if not cur:node = TreeNode(val)if self.parent.val > val:self.parent.left = nodeelse:self.parent.right = nodereturnself.parent = curif cur.val > val:self.reversal(cur.left, val)else:self.reversal(cur.right, val)def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if not root:return TreeNode(val)cur = rootself.reversal(cur, val)return root# ***********************************************************************# 迭代法
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:node = TreeNode(val)if not root:return TreeNode(val)cur = rootwhile cur:parent = curif cur.val > val:cur = cur.leftelse:cur = cur.rightif parent.val > val:parent.left = nodeelse:parent.right = nodereturn root

java

450.删除二叉搜索树中的节点  

题目链接

        力扣题目链接

题目难度

        中等

看到题目的第一想法

        没接触过，看到就觉得有点难！

看完代码随想录的总结

文章讲解

        代码随想录文字讲解

视频讲解

        代码随想录视频讲解

解题思路

        1. 递归法（关键单层递归中的情况梳理）

            递归三步曲：

            1）入参：根节点和要比较的值；返回值：删除节点以后要返回的节点（用于上一层递归来赋值）。

            2）终止条件：有五种情况：第一种：节点空则返回空，说明没找到要删除的节点；第二种：遍历到的要删除的节点此时左右节点均为空，那么直接返回空；第三种：遍历到要删除的节点此时左节点不为空右节点为空，那么直接返回左节点；第四种情况：遍历到要删除的节点此时左节点空右节点不为空，那么直接返回右节点；第五种：遍历到要删除的节点了此时左右子节点都不为空，此时需要把左子树放到右子树当中（将删除节点的左子树头结点放到删除节点的右子树的最左面节点的左孩子上），整个时候就成了左节点空右节点非空的情况，返回右节点。

            3）单层递归逻辑：遍历左子树，遍历右子树，如果不满足上边终止条件则返回当前节点。

代码编写

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def reversal(self, root, key):if not root:return rootif root.val == key:if not root.left and not root.right:return Noneelif root.left and not root.right:return root.leftelif not root.left and root.right:return root.rightelse:cur = root.rightwhile(cur.left):cur = cur.leftcur.left = root.leftreturn root.rightif root.val > key:root.left = self.reversal(root.left, key)else:root.right = self.reversal(root.right, key)return rootdef deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:return self.reversal(root, key)

java

今日总结

        今天的题目也都是二叉搜索树的题目，做二叉搜索树的题目，还是要注意利用其特性。在删除和插入二叉树节点的时候使用递归，可以利用返回值进行节点赋值的操作，这样比较简单不用重复去判断条件。