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

目录235. 二叉搜索树的最近公共祖先题目描述解题思路701. 二叉搜索树中的插入操作题目描述解题思路450. 删除二叉搜索树中的节点题目描述解题思路235. 二叉搜索树的最近公共祖先题目描述给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”解题思路和236. 二叉树的最近公共祖先类似二叉搜索树可以对其进行优化当pq值都小于根节点时说明在左子树当pq值都大于根节点时说明在右子树特殊的是当pq分别在左右子树时此时的根节点为最近公共祖先。不可能存在次近公共祖先所谓的该次近公共祖先一定是在某个根节点下的左子树或者右子树class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: if not root:return root #pq都小于根节点 if root.val p.val and root.val q.val: left self.lowestCommonAncestor(root.left,p,q) if left:return left #pq都大于根节点 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