代码随想录算法训练营第二十天 |235、二叉搜索树的最近巩固祖先 701、二叉搜索树中的插入操作 450、删除二叉搜索树中的节点
目录
235. 二叉搜索树的最近公共祖先
题目描述
解题思路
701. 二叉搜索树中的插入操作
题目描述
解题思路
450. 删除二叉搜索树中的节点
题目描述
解题思路
235. 二叉搜索树的最近公共祖先
题目描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
解题思路
- 和236. 二叉树的最近公共祖先类似，二叉搜索树可以对其进行优化
- 当pq值都小于根节点时，说明在左子树；当pq值都大于根节点时，说明在右子树；特殊的是，当p，q分别在左右子树时，此时的根节点为最近公共祖先。不可能存在次近公共祖先，所谓的该次近公共祖先一定是在某个根节点下的左子树或者右子树
class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if not root:return root #p，q都小于根节点 if root.val > p.val and root.val > q.val: left = self.lowestCommonAncestor(root.left,p,q) if left:return left #p，q都大于根节点 if root.val < p.val and root.val < q.val: right = self.lowestCommonAncestor(root.right,p,q) if right:return right #最近公共祖先 return root701. 二叉搜索树中的插入操作
题目描述
给定二叉搜索树（BST）的根节点
root和要插入树中的值value，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
解题思路
- 三部曲
- 递归类型：不涉及处理中间节点操作
- 参数：根节点，插入值
- 递归终止条件：当前节点为叶子节点，可以插入，否则就继续向下执行
class Solution: def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]: if not root: return TreeNode(val) #小于根节点，在根节点的左子树 if root.val > val: root.left = self.insertIntoBST(root.left,val) #大于根节点，在根节点的右子树 if root.val < val: root.right = self.insertIntoBST(root.right,val) return root450. 删除二叉搜索树中的节点
题目描述
给定一个二叉搜索树的根节点root和一个值key，删除二叉搜索树中的key对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
解题思路
- 三部曲
- 递归类型：不单独涉及中间节点，前中后序都可以
- 参数：根节点和目标删除节点
- 递归终止条件：分五种情况，如下
- 难点在当删除节点为根节点时，并且左右子树不为空时需要改变树的结构，此时将右子树的根节点设为树的根节点时，就将左子树挂在右子树的最左侧；将左子树的根节点设为树的根节点时，就将右子树挂在左子树的最右侧
class Solution: def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]: #1.树为空，没有找到删除节点 if not root: return None #2.找到删除节点 if root.val == key: #2.1叶子节点 if not root.left and not root.right: return None #2.2左为空右不为空 if not root.left and root.right: return root.right #2.3左不为空右为空 if root.left and not root.right: return root.left #2.4左右都不为空（改变树的结构） else: #将右节点作为根节点 #由于左子树严格小于右子树，故将左子树的根节点放在右子树的最左侧 cur = root.right while cur.left:cur = cur.left #此时cur.left为空 cur.left = root.left #返回右子树的根节点作为新树的根节点 return root.right #3.在左右子树中寻找 if key < root.val: root.left = self.deleteNode(root.left,key) if key > root.val: root.right = self.deleteNode(root.right,key) return root