代码随想录day8

1.合并二叉树力扣题目链接(opens new window)给定两个二叉树想象当你将它们中的一个覆盖到另一个上时两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠那么将他们的值相加作为节点合并后的新值否则不为 NULL 的节点将直接作为新二叉树的节点。class Solution { public: TreeNode* creat(TreeNode* root1,TreeNode* root2){ if(root1nullptrroot2!nullptr){ return root2; } if(root1!nullptrroot2nullptr){ return root1; } if(root1nullptrroot2nullptr){ return nullptr; } TreeNode* rootnew TreeNode(); root-valroot1-valroot2-val; root-leftcreat(root1-left,root2-left); root-rightcreat(root1-right,root2-right); return root; } TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { return creat(root1,root2); } };属于二叉树的创建题目参数为两个节点返回值是节点类型终止条件为四种两个节点的存在情况单次递归逻辑为创建新节点为新节点赋值之后创建左右节点。返回当前节点2.二叉搜索树中的搜索力扣题目地址(opens new window)给定二叉搜索树BST的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在则返回 NULL。class Solution { public: TreeNode* searchBST(TreeNode* root, int val) { if(rootnullptr){ return nullptr; } if(root-valval){ return root; }else if(root-valval){ return searchBST(root-left,val); }else{ return searchBST(root-right,val); } } };根据二叉搜索树的特点直接二分法递归遍历即可。3.验证二叉搜索树力扣题目链接(opens new window)给定一个二叉树判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树class Solution { public: vectorint res; void travel(TreeNode* root){ if(rootnullptr){ return; } travel(root-left); res.push_back(root-val); travel(root-right); } bool isValidBST(TreeNode* root) { travel(root); for(int i1;ires.size();i){ if(res[i]res[i-1]){ return false; } } return true; } };这里直接使用中序遍历得到的数组应该是一个升序的数组即为二叉搜索树4.二叉搜索树的最小绝对差力扣题目链接(opens new window)给你一棵所有节点为非负值的二叉搜索树请你计算树中任意两节点的差的绝对值的最小值。class Solution { public: TreeNode* prenullptr; int resultINT_MAX; void dfs(TreeNode* root){ if(rootnullptr){ return ; } dfs(root-left); if(pre){ resultmin(result,root-val-pre-val); } preroot; dfs(root-right); } int getMinimumDifference(TreeNode* root) { dfs(root); return result; } };最直观的方式是中序遍历记录在数组中之后遍历一遍记录最小值这样内存占比较大可以直接在遍历二叉树中就记录下最小的差只需要两个指针就可以了一个是pre代表前一个节点root代表当前节点。5.二叉搜索树中的众数力扣题目链接(opens new window)给定一个有相同值的二叉搜索树BST找出 BST 中的所有众数出现频率最高的元素。假定 BST 有如下定义结点左子树中所含结点的值小于等于当前结点的值结点右子树中所含结点的值大于等于当前结点的值左子树和右子树都是二叉搜索树class Solution { public: TreeNode* prenullptr; int count0; int maxcount0; vectorint result; void searchBST(TreeNode* root){ if(rootnullptr){ return ; } searchBST(root-left);//左 if(prenullptr){//中 count1; }else if(pre-valroot-val){//相等时频率加一 count; }else{ count1; } preroot;//更新上一个节点 if(countmaxcount){ result.push_back(root-val); } if(countmaxcount){ maxcountcount; result.clear(); result.push_back(root-val); } searchBST(root-right);//右 } vectorint findMode(TreeNode* root) { searchBST(root); return result; } };一种方式也是直接中序遍历得到的是有序数组之后使用map哈希表记录下元素的出现次数之后得到众数。这种方式的弊端是在获得众数是不能直接堆哈希表进行排序还需要转换成vectorpairint,int来进行再次的排序并且由于不只一个最大的频率还需要再遍历一遍数组。另一种方式是使用双指针在进行递归遍历二叉树的时候就可以统计出众数if(prenullptr){//中 count1; }else if(pre-valroot-val){//相等时频率加一 count; }else{ count1; } preroot;//更新上一个节点 if(countmaxcount){ result.push_back(root-val); } if(countmaxcount){ maxcountcount; result.clear(); result.push_back(root-val); }使用中序遍历中对节点的处理逻辑一个指针用于记录上一个节点当上一个节点为空说明已经遍历到了最左边数量记为1当前节点值与上一个节点值相等的时候说明元素重复了数量不相等的时候说明遇到新的元素重新为1。之后更新节点当当前的数量与最大的数量相等的时候就加入到结果数组中大于最大数量的时候就更新最大数量并且要先清除结果数组中的元素因为有了最大值了再加入新的元素。6.二叉树的最近公共祖先力扣题目链接(opens new window)给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(rootNULL||rootp||rootq)return root; TreeNode* leftlowestCommonAncestor(root-left,p,q); TreeNode* rightlowestCommonAncestor(root-right,p,q); if(left!NULLright!NULL){ return root; }else if(left!NULLrightNULL){ return left; }else { return right; } } };参数为根节点与两个需要判断的pq节点返回值为根节点函数目的是找到pq的最近公共祖先终止条件是节点为空遇到p节点或者遇到q节点就返回当前节点定义左右两个节点为当前节点的左右孩子为参数的两个节点的公共祖先当左右都为空的时候说明当前节点就是最近的左节点为空说明最近公共祖先是右节点右节点为空说明是左边节点。7.二叉搜索树的最近公共祖先力扣题目链接(opens new window)给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”class Solution { public: TreeNode* dfs(TreeNode* root,TreeNode* p,TreeNode* q){ if(rootNULL){ return NULL; } if(root-valp-valroot-valq-val){ TreeNode* leftdfs(root-left,p,q); if(left!NULL){ return left; } } if(root-valp-valroot-valq-val){ TreeNode* rightdfs(root-right,p,q); if(right!NULL){ return right; } } return root; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { return dfs(root,p,q); } };与上一题类似不过可以利用二叉搜索树的特点来进行判断大抵是使用二分的概念当前节点的值在这两个节点的中间的时候说明当前节点就是最近的公共祖先。当大于这两个节点的值的时候就计算出左节点为根节点时的祖先不为空就直接返回左节点。小于这两个节点的值也是类似。8.二叉搜索树中的插入操作力扣题目链接(opens new window)给定二叉搜索树BST的根节点和要插入树中的值将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证新值和原始二叉搜索树中的任意节点值都不同。注意可能存在多种有效的插入方式只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if(root nullptr){ return new TreeNode(val); } if(root-val val){ // 值更小插入左子树 root-left insertIntoBST(root-left, val); }else{ // 值更大插入右子树 root-right insertIntoBST(root-right, val); } return root; } };这里是需要返回值的返回值就是根节点函数目的是以当前节点为根节点插入节点并且返回根节点终止条件是节点为空返回并创建目标值节点与当前节点比较大小比当前节点值大就插入到右子树中以右子树为根节点进行递归插入比当前节点值小也是类似的逻辑。最后返回根节点。9.删除二叉搜索树中的节点力扣题目链接(opens new window)给定一个二叉搜索树的根节点 root 和一个值 key删除二叉搜索树中的 key 对应的节点并保证二叉搜索树的性质不变。返回二叉搜索树有可能被更新的根节点的引用。一般来说删除节点可分为两个步骤首先找到需要删除的节点 如果找到了删除它。 说明 要求算法时间复杂度为 $O(h)$h 为树的高度。class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if(rootnullptr){ return root; } if(keyroot-val){ if(!root-left!root-right){ delete root; return nullptr; }else if(root-left!root-right){ TreeNode* noderoot-left; delete root; return node; }else if(root-right!root-left){ TreeNode* noderoot-right; delete root; return node; }else { TreeNode* curroot-right; while(cur-left!nullptr){ curcur-left; } cur-leftroot-left; TreeNode* tmproot; rootroot-right; delete tmp; return root; } } if(root-valkey){ root-leftdeleteNode(root-left,key); } if(root-valkey){ root-rightdeleteNode(root-right,key); } return root; } };函数目的是删除以当前节点为根节点时的指定元素节点这里需要删除节点就需要修改树的结构了遇到节点时需要删除还需要分情况讨论1.是叶子节点直接删除返回空2.左节点存在右节点不存在删除节点返回左子树3.左节点不存在右节点存在删除节点返回右子树4.左右节点都存在需要把左子树放在右子树的最左下角循环向下遍历到右子树的左节点直到叶子节点把左子树放在叶子节点下然后删除节点返回右子树。没遇到节点就需要递归遍历了大于当前节点就递归右子树当前节点右节点为以右节点为根节点删除元素的返回值。小于当前节点就递归左子树。最后返回根节点。10.修建二叉搜索树力扣题目链接(opens new window)给定一个二叉搜索树同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树使得所有节点的值在[L, R]中 (RL) 。你可能需要改变树的根节点所以结果应当返回修剪好的二叉搜索树的新的根节点。class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { if(rootnullptr) return nullptr; if(root-valhigh){ return trimBST(root-left,low,high); } if(root-vallow){ return trimBST(root-right,low,high); } root-lefttrimBST(root-left,low,high); root-righttrimBST(root-right,low,high); return root; } };这里也是需要递归的函数目的是修剪以当前节点为根节点时的树终止条件是遇到空节点就返回空当节点不在修剪范围的时候就直接返回对应一半的修剪的树节点在修剪范围内的时候左节点返回值为以左节点为根节点的修剪过的子树右节点类似最后返回根节点。11.有序数组转换为二叉搜索树力扣题目链接(opens new window)将一个按照升序排列的有序数组转换为一棵高度平衡二叉搜索树。本题中一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。class Solution { public: TreeNode* creatBst(vectorint nums,int left,int right){//创建left到right的子树 if(leftright){ return nullptr; } int midleft((right-left)/2);//因为要平衡所以选择中间元素 TreeNode* nodenew TreeNode(nums[mid]); node-leftcreatBst(nums,left,mid-1); node-rightcreatBst(nums,mid1,right); return node; } TreeNode* sortedArrayToBST(vectorint nums) { return creatBst(nums,0,nums.size()-1); } };这里需要构建的是平衡二叉搜索树高度差有限制所以选择根节点就需要选择数组中间的元素之后划分两端长度进行再次构建节点。使用的是左闭右闭的区间参数是数组左右两个区间的索引。12.二叉搜索树转换为累加树力扣题目链接(opens new window)给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。提醒一下二叉搜索树满足下列约束条件节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。class Solution { public: int num0; TreeNode* convertBST(TreeNode* root) {//反向中序遍历 if(rootnullptr) return nullptr; root-rightconvertBST(root-right); root-valroot-valnum; numroot-val; root-leftconvertBST(root-left); return root; } };这里直接使用中序反向遍历就可以了先便利右节点到叶子节点之后更新节点的值再更新num的值之后遍历左节点。