代码随想录算法训练营第十五天

学习内容235. 二叉搜索树的最近公共祖先给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”例如给定如下二叉搜索树: root [6,2,8,0,4,7,9,null,null,3,5]classSolution:deftraversal(self,cur,p,q):ifcurisNone:returncur# 中ifcur.valp.valandcur.valq.val:# 左returnself.traversal(cur.left,p,q)ifcur.valp.valandcur.valq.val:# 右returnself.traversal(cur.right,p,q)returncurdeflowestCommonAncestor(self,root,p,q):returnself.traversal(root,p,q)学习心得注意判断条件就行返回的就是公共祖先。比二叉树的最近公共祖先简单。701. 二叉搜索树中的插入操作给定二叉搜索树BST的根节点 root 和要插入树中的值 value 将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 新值和原始二叉搜索树中的任意节点值都不同。注意可能存在多种有效的插入方式只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。classSolution:def__init__(self):self.parentNonedeftraversal(self,cur,val):ifcurisNone:nodeTreeNode(val)ifvalself.parent.val:self.parent.rightnodeifvalself.parent.val:self.parent.leftnodereturnself.parentcurifcur.valval:self.traversal(cur.left,val)ifcur.valval:self.traversal(cur.right,val)definsertIntoBST(self,root,val):self.parentTreeNode(0)ifrootisNone:returnTreeNode(val)self.traversal(root,val)returnroot学习心得注意判断条件如果递归到空则说明遇到了可插入结点的位置再判断插入到左边还是右边。 self.parent节点就是要插入结点的母节点。450. 删除二叉搜索树中的节点给定一个二叉搜索树的根节点 root 和一个值 key删除二叉搜索树中的 key 对应的节点并保证二叉搜索树的性质不变。返回二叉搜索树有可能被更新的根节点的引用。一般来说删除节点可分为两个步骤首先找到需要删除的节点如果找到了删除它。classSolution:defdeleteNode(self,root:Optional[TreeNode],key:int)-Optional[TreeNode]:ifrootisNone:returnrootifroot.valkey:ifroot.leftNoneandroot.rightNone:returnNoneelifroot.leftisNone:returnroot.rightelifroot.rightisNone:returnroot.leftelse:curroot.rightwhilecur.leftisnotNone:curcur.left cur.leftroot.leftreturnroot.rightifroot.valkey:root.leftself.deleteNode(root.left,key)ifroot.valkey:root.rightself.deleteNode(root.right,key)returnroot学习心得删除节点本质是母节点指向删除节点的下一个节点判断四种情况删除结点没有子节点直接返回none。左边有右边没有返回左边左右两边都有则进入下一个环节。首先处理右边定义cur为右节点while循环找到右节点的最左边子节点之后让其的左边指向母节点的左边即可。二叉搜索树的性质左边比右边小。669. 修剪二叉搜索树给你二叉搜索树的根节点 root 同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即如果没有被移除原有的父代子代关系都应当保留)。 可以证明存在 唯一的答案 。所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。输入root [1,0,2], low 1, high 2输出[1,null,2]输入root [3,0,4,null,2,null,null,1], low 1, high 3输出[3,2,null,1]classSolution:deftrimBST(self,root:Optional[TreeNode],low:int,high:int)-Optional[TreeNode]:ifrootisNone:returnNoneifroot.vallow:returnself.trimBST(root.right,low,high)ifroot.valhigh:returnself.trimBST(root.left,low,high)root.leftself.trimBST(root.left,low,high)root.rightself.trimBST(root.right,low,high)returnroot学习心得本质就是把在边界外的点找出来。108. 将有序数组转换为二叉搜索树给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 平衡 二叉搜索树。输入nums [-10,-3,0,5,9]输出[0,-3,9,-10,null,5]解释[0,-10,5,null,-3,null,9] 也将被视为正确答案输入nums [1,3]输出[3,1]解释[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。classSolution:deftraversal(self,nums,left,right):ifleftright:returnNonemidleft(right-left)//2rootTreeNode(nums[mid])root.leftself.traversal(nums,left,mid-1)root.rightself.traversal(nums,mid1,right)returnrootdefsortedArrayToBST(self,nums:List[int])-Optional[TreeNode]:rootself.traversal(nums,0,len(nums)-1)returnroot学习心得注意终止条件左边指针大于右边。在左右区间一直递归赋值就行。538. 把二叉搜索树转换为累加树给出二叉 搜索 树的根节点 root该树的节点值各不相同请你将其转换为累加树Greater Sum Tree将其转换为一个更大的树使得原始二叉搜索树中的每个节点值都变为原本值加上原本二叉搜索树中所有比该节点值大的节点值的总和。提醒一下二叉搜索树满足下列约束条件节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。classSolution:defconvertBST(self,root:Optional[TreeNode])-Optional[TreeNode]:self.pre0self.traversal(root)returnrootdeftraversal(self,cur):ifcurisNone:returnself.traversal(cur.right)cur.valself.pre self.precur.val self.traversal(cur.left)学习心得从最右边子节点开始每前一个节点就是加上他后面节点的总值。self.pre为记录总值的。相当于给每一个当前节点重新加上pre赋值。右中左。