免费的网站生成app,做网站廊坊,杭州设计公司网站排名,淘宝店铺800一个收购654.最大二叉树
分析#xff1a;相比较遍历顺序构建二叉树#xff0c;这个相对简单。
思路#xff1a;每次找到数组最大值#xff0c;然后分割数组 class Solution {
public:TreeNode*judge(vectorintnums){if(nums.size()0) return nullptr;int maxNum0,in…654.最大二叉树
分析相比较遍历顺序构建二叉树这个相对简单。
思路每次找到数组最大值然后分割数组 class Solution {
public:TreeNode*judge(vectorintnums){if(nums.size()0) return nullptr;int maxNum0,index0;for(int i0;inums.size();i){//获取最大值和下标if(nums[i]maxNum){maxNumnums[i];indexi;}}TreeNode*rootnew TreeNode(maxNum);if(nums.size()1) return root;//切割左子树和右子树vectorint leftNums(nums.begin(),nums.begin()index);vectorint rightNums(nums.begin()index1,nums.end());root-leftjudge(leftNums);root-rightjudge(rightNums);return root;}TreeNode* constructMaximumBinaryTree(vectorint nums) {//思路每次找到数组中最大值然后进行左右切割return judge(nums);}
};
617.合并二叉树
思路一创建一个新的二叉树每次同时传入二叉树的同一位置
class Solution {
public:TreeNode* judge(TreeNode*root1,TreeNode*root2){if(root1nullptr root2nullptr) return nullptr;TreeNode*newNodenew TreeNode();if(root1!nullptr root2!nullptr){newNode-valroot1-valroot2-val;newNode-leftjudge(root1-left,root2-left);newNode-rightjudge(root1-right,root2-right);} if(root1nullptr root2!nullptr){newNode-valroot2-val;newNode-leftjudge(nullptr,root2-left);newNode-rightjudge(nullptr,root2-right);} if(root1!nullptr root2nullptr){newNode-valroot1-val;newNode-leftjudge(root1-left,nullptr);newNode-rightjudge(root1-right,nullptr);} return newNode;}TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//思路直接同时遍历两个二叉树子节点不存在传入下一个为空指针if(root1nullptr) return root2;if(root2nullptr) return root1;if(root1nullptr root2nullptr) return nullptr;return judge(root1,root2);}
};
思路二以其中一棵二叉树作为返回值尽量不创建节点
class Solution {
public:TreeNode* judge(TreeNode*root1,TreeNode*root2){if(root1nullptr root2nullptr) return nullptr;if(root1!nullptr root2!nullptr){root1-valroot2-val;root1-leftjudge(root1-left,root2-left);root1-rightjudge(root1-right,root2-right);} else if(root1nullptr root2!nullptr){TreeNode*newNodenew TreeNode();newNode-valroot2-val;newNode-leftjudge(nullptr,root2-left);newNode-rightjudge(nullptr,root2-right);return newNode;} return root1;}TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//思路直接同时遍历两个二叉树子节点不存在传入下一个为空指针if(root1nullptr) return root2;if(root2nullptr) return root1;if(root1nullptr root2nullptr) return nullptr;root1-valroot2-val;root1-leftjudge(root1-left,root2-left);root1-rightjudge(root1-right,root2-right);return root1;}
};
700.二叉搜索树中的搜索
思路判断大小搜索
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {//思路找到节点然后返回//分析左子节点比父节点小右子节点比父节点大if(rootnullptr)return root;TreeNode*newNoderoot;;if(newNode-valval)newNodesearchBST(newNode-left,val);else if(newNode-valval)newNodesearchBST(newNode-right,val);return newNode;}
};
98.验证二叉搜素树
思考从二叉搜索树的特性入手二叉搜索树的中序遍历必然是递增序列
分析细节方面很要注意
class Solution {
public:vectorintans;void judge(TreeNode*root){if(rootnullptr) return;judge(root-left);ans.push_back(root-val);judge(root-right);}bool isValidBST(TreeNode* root) {//思路直接分析//思路二中序遍历的数组一定递增judge(root);if(ans.size()1) return true;int preans[0];for(int i1;ians.size();i){if(ans[i]pre)return false;preans[i];}return true;}
};
530.二叉搜索树的最小绝对差
思路把所有节点加入数组排序后两两计算最小差值
class Solution {
public:vectorintans;void judge(TreeNode*root){if(rootnullptr) return;ans.push_back(root-val);judge(root-left);judge(root-right);}int getMinimumDifference(TreeNode* root) {//思路把父节点的值传入子节点然后更新最小差值//问题题目要求是任意节点所以考虑先加入数组排序后两两计算judge(root);sort(ans.begin(),ans.end());int minSubINT_MAX;for(int i1;ians.size();i){int midabs(ans[i-1]-ans[i]);minSubmin(minSub,mid);}return minSub;}
};
501.二叉搜索树中的众数
分析众数就是出现多次的数 思路使用哈希表递归遍历所有节点
class Solution {
public:vectorintres;unordered_mapint,intmap;void judge(TreeNode*root){if(rootnullptr)return;map[root-val];//记录出现的次数judge(root-left);judge(root-right);}vectorint findMode(TreeNode* root) {judge(root);int maxNum0;for(auto it:map){//第一次遍历获取出现最大频率if(it.secondmaxNum) maxNumit.second;}for(auto it:map){//找到众数if(it.secondmaxNum) res.push_back(it.first);}return res;}
};
236.二叉树的最近公共树祖先
思路一通过左0右1获取两个节点的遍历路径然后截取两个节点相同的遍历路径使用相同的遍历路径直接获得最近公共树祖先
class Solution {
public:string midP,midQ;void judge(TreeNode*root,string judgeDist,TreeNode*p,TreeNode*q,string midP1,string midQ1){if(rootnullptr) return;midP1judgeDist;midQ1judgeDist;if(rootp) midPmidP1;if(rootq) midQmidQ1;judge(root-left,0,p,q,midP1,midQ1);judge(root-right,1,p,q,midP1,midQ1); }TreeNode*search(TreeNode*root,queuechar mid,int start){TreeNode*cur;if(mid.size()0)return root;//分两种情况if(mid.front()1){mid.pop();cursearch(root-right,mid,start1);} else{mid.pop();cursearch(root-left,mid,start1);} return cur;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//思路遍历二叉树给左右子节点分别编号找到两个节点之后匹配编号的相同位数//然后用相同位数走到的那个节点就是最近公共祖先int i;queuecharque;judge(root,,p,q,,);//coutmidP.size()midQ.size();for(i0;imidP.size();i){if(midP[i]!midQ[i]) break;elseque.push(midP[i]);}//cout1;if(i0) return root;string midmidP.substr(0,i);coutmid.size()endl;return search(root,que,0);}
};
235.二叉搜索树的最近公共祖先
思路一比较出节点值大小然后从根节点开始判断两个节点的位置
class Solution {
public:TreeNode* judge(TreeNode*root,TreeNode*first,TreeNode*second){//祖先节点在当前root上或者两个节点在当前root的两边if((first-valroot-val second-valroot-val) || (first-valroot-val second-valroot-val)) return root;TreeNode*res;//当前两个节点在同一边if(first-valroot-val second-valroot-val)resjudge(root-left,first,second);else if(first-valroot-val second-valroot-val)resjudge(root-right,first,second);return res;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//思路找到一个在两个节点中间的节点或者等于较小值//比较出最小值if(p-valq-val) return judge(root,q,p);return judge(root,p,q);}
};
701.二叉搜索树的插入操作
思路一直接遍历插入
class Solution {
public:void judge(TreeNode*root,int val){if(root-valval){//需要插入左边if(root-left) judge(root-left,val);else{TreeNode*newNodenew TreeNode(val);root-leftnewNode;}}else{//需要插入右边if(root-right) judge(root-right,val);else{TreeNode*newNodenew TreeNode(val);root-rightnewNode;}}}TreeNode* insertIntoBST(TreeNode* root, int val) {if(rootnullptr){//考虑没有节点的情况return new TreeNode(val);}judge(root,val);return root;}
};
450.删除二叉搜索树的节点
分析这题做的好复杂感觉饶了很多弯子100多行居然还超过了68%哈哈哈哈哈
思路一 1.考虑特殊情况根节点不存在和要删除根节点。 2.考虑二叉树中没有要删除的节点。 3.递归遍历寻找left或者right是否为要删除的节点当找到时将root和要删除的子节点传入res删除函数其中变量judgeB判断是左子节点还是右子节点。 4.在删除节点时需要判断该节点是否有左右子节点都有的情况下需要使用add函数将要删除的节点的左子节点放到右子节点的下面。使用add递归添加
class Solution {
public:bool judgeAfalse;void add(TreeNode*root,TreeNode*node){//用于删除节点时组合该节点的两个子节点if(nodenullptr) return;if(root-valnode-val){//插入节点在左边if(root-left)add(root-left,node);elseroot-leftnode;}else{//插入节点在右边if(root-right)add(root-right,node);elseroot-rightnode;}}void res(TreeNode*root,TreeNode*node, bool judgeB){//用于删除节点if(judgeB)//左子节点{if(node-leftnullptr node-rightnullptr){//key值节点为叶子节点root-leftnullptr;return;}else if(node-left node-right){//key值节点有左右节点root-leftnode-right;add(node-right,node-left);return;}else if(node-left !node-right)root-leftnode-left;elseroot-leftnode-right;}else{if(node-leftnullptr node-rightnullptr){//key值节点为叶子节点root-rightnullptr;return;}else if(node-left node-right){//key值节点有左右节点root-rightnode-right;add(node-right,node-left);return;}else if(node-left !node-right)root-rightnode-left;elseroot-rightnode-right;}}void judge(TreeNode*root,int key){//用于查找删除节点if(rootnullptr)return;if(root-valkey){//当父节点大于key说明key在左边if(root-left-valkey){//当左子节点等于key时res(root,root-left,true);}elsejudge(root-left,key);}else if(root-valkey){if(root-right-valkey){res(root,root-right,false);}elsejudge(root-right,key);}}void judgeMax(TreeNode*root,int key){//用于判断二叉树中是否存在目标节点if(rootnullptr) return;if(root-valkey) judgeAtrue;if(root-valkey) judgeMax(root-left,key);if(root-valkey) judgeMax(root-right,key);}TreeNode* deleteNode(TreeNode* root, int key) {//思路遍历二叉树找到节点时判断当前节点左右两边情况//if(rootnullptr) return root;if(root-valkey){if(root-left root-right){add(root-right,root-left);return root-right;}else if(root-left) return root-left;else if(root-right) return root-right;elsereturn nullptr;}judgeMax(root,key);if(judgeAfalse){cout123;return root;} judge(root,key);return root;}
};
