654.最大二叉树
分析:相比较遍历顺序构建二叉树,这个相对简单。
思路:每次找到数组最大值,然后分割数组
class Solution {
public:
TreeNode*judge(vector<int>&nums){
if(nums.size()==0) return nullptr;
int maxNum=0,index=0;
for(int i=0;i<nums.size();i++){//获取最大值和下标
if(nums[i]>maxNum){
maxNum=nums[i];
index=i;
}
}
TreeNode*root=new TreeNode(maxNum);
if(nums.size()==1) return root;
//切割左子树和右子树
vector<int> leftNums(nums.begin(),nums.begin()+index);
vector<int> rightNums(nums.begin()+index+1,nums.end());
root->left=judge(leftNums);
root->right=judge(rightNums);
return root;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
//思路:每次找到数组中最大值,然后进行左右切割
return judge(nums);
}
};
617.合并二叉树
思路一:创建一个新的二叉树,每次同时传入二叉树的同一位置
class Solution {
public:
TreeNode* judge(TreeNode*root1,TreeNode*root2){
if(root1==nullptr && root2==nullptr) return nullptr;
TreeNode*newNode=new TreeNode();
if(root1!=nullptr && root2!=nullptr){
newNode->val=root1->val+root2->val;
newNode->left=judge(root1->left,root2->left);
newNode->right=judge(root1->right,root2->right);
}
if(root1==nullptr && root2!=nullptr){
newNode->val=root2->val;
newNode->left=judge(nullptr,root2->left);
newNode->right=judge(nullptr,root2->right);
}
if(root1!=nullptr && root2==nullptr){
newNode->val=root1->val;
newNode->left=judge(root1->left,nullptr);
newNode->right=judge(root1->right,nullptr);
}
return newNode;
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
//思路:直接同时遍历两个二叉树,子节点不存在传入下一个为空指针
if(root1==nullptr) return root2;
if(root2==nullptr) return root1;
if(root1==nullptr && root2==nullptr) return nullptr;
return judge(root1,root2);
}
};
思路二:以其中一棵二叉树作为返回值,尽量不创建节点
class Solution {
public:
TreeNode* judge(TreeNode*root1,TreeNode*root2){
if(root1==nullptr && root2==nullptr) return nullptr;
if(root1!=nullptr && root2!=nullptr){
root1->val+=root2->val;
root1->left=judge(root1->left,root2->left);
root1->right=judge(root1->right,root2->right);
}
else if(root1==nullptr && root2!=nullptr){
TreeNode*newNode=new TreeNode();
newNode->val=root2->val;
newNode->left=judge(nullptr,root2->left);
newNode->right=judge(nullptr,root2->right);
return newNode;
}
return root1;
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
//思路:直接同时遍历两个二叉树,子节点不存在传入下一个为空指针
if(root1==nullptr) return root2;
if(root2==nullptr) return root1;
if(root1==nullptr && root2==nullptr) return nullptr;
root1->val+=root2->val;
root1->left=judge(root1->left,root2->left);
root1->right=judge(root1->right,root2->right);
return root1;
}
};
700.二叉搜索树中的搜索
思路:判断大小,搜索
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
//思路:找到节点,然后返回
//分析:左子节点比父节点小,右子节点比父节点大
if(root==nullptr)
return root;
TreeNode*newNode=root;;
if(newNode->val>val)
newNode=searchBST(newNode->left,val);
else if(newNode->val<val)
newNode=searchBST(newNode->right,val);
return newNode;
}
};
98.验证二叉搜素树
思考:从二叉搜索树的特性入手,二叉搜索树的中序遍历必然是递增序列
分析:细节方面很要注意
class Solution {
public:
vector<int>ans;
void judge(TreeNode*root){
if(root==nullptr) 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 pre=ans[0];
for(int i=1;i<ans.size();i++){
if(ans[i]<=pre)
return false;
pre=ans[i];
}
return true;
}
};
530.二叉搜索树的最小绝对差
思路:把所有节点加入数组,排序后两两计算最小差值
class Solution {
public:
vector<int>ans;
void judge(TreeNode*root){
if(root==nullptr) return;
ans.push_back(root->val);
judge(root->left);
judge(root->right);
}
int getMinimumDifference(TreeNode* root) {
//思路:把父节点的值传入子节点,然后更新最小差值
//问题:题目要求是任意节点,所以考虑先加入数组,排序后两两计算
judge(root);
sort(ans.begin(),ans.end());
int minSub=INT_MAX;
for(int i=1;i<ans.size();i++){
int mid=abs(ans[i-1]-ans[i]);
minSub=min(minSub,mid);
}
return minSub;
}
};
501.二叉搜索树中的众数
分析:众数就是出现多次的数
思路:使用哈希表,递归遍历所有节点
class Solution {
public:
vector<int>res;
unordered_map<int,int>map;
void judge(TreeNode*root){
if(root==nullptr)
return;
map[root->val]++;//记录出现的次数
judge(root->left);
judge(root->right);
}
vector<int> findMode(TreeNode* root) {
judge(root);
int maxNum=0;
for(auto it:map){//第一次遍历获取出现最大频率
if(it.second>maxNum) maxNum=it.second;
}
for(auto it:map){//找到众数
if(it.second==maxNum) 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(root==nullptr) return;
midP1+=judgeDist;
midQ1+=judgeDist;
if(root==p) midP=midP1;
if(root==q) midQ=midQ1;
judge(root->left,"0",p,q,midP1,midQ1);
judge(root->right,"1",p,q,midP1,midQ1);
}
TreeNode*search(TreeNode*root,queue<char> mid,int start){
TreeNode*cur;
if(mid.size()==0)
return root;
//分两种情况
if(mid.front()=='1'){
mid.pop();
cur=search(root->right,mid,start+1);
}
else{
mid.pop();
cur=search(root->left,mid,start+1);
}
return cur;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//思路:遍历二叉树,给左右子节点分别编号,找到两个节点之后匹配编号的相同位数,
//然后用相同位数走到的那个节点就是最近公共祖先
int i;
queue<char>que;
judge(root,"",p,q,"","");
//cout<<midP.size()<<midQ.size();
for(i=0;i<midP.size();i++)
{
if(midP[i]!=midQ[i]) break;
else
que.push(midP[i]);
}
//cout<<1;
if(i==0) return root;
string mid=midP.substr(0,i);
cout<<mid.size()<<endl;
return search(root,que,0);
}
};
235.二叉搜索树的最近公共祖先
思路一:比较出节点值大小,然后从根节点开始判断两个节点的位置
class Solution {
public:
TreeNode* judge(TreeNode*root,TreeNode*first,TreeNode*second){
//祖先节点在当前root上或者两个节点在当前root的两边
if(first->val<=root->val && second->val>=root->val)
return root;
TreeNode*res;
//当前两个节点在同一边
if(second->val<root->val)
res=judge(root->left,first,second);
else
res=judge(root->right,first,second);
return res;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//思路:找到一个在两个节点中间的节点,或者等于较小值
//比较出最小值
if(p->val>q->val) return judge(root,q,p);
return judge(root,p,q);
}
};
701.二叉搜索树的插入操作
思路一:直接遍历插入
class Solution {
public:
void judge(TreeNode*root,int val){
if(root->val>val){//需要插入左边
if(root->left) judge(root->left,val);
else{
TreeNode*newNode=new TreeNode(val);
root->left=newNode;
}
}
else{//需要插入右边
if(root->right) judge(root->right,val);
else{
TreeNode*newNode=new TreeNode(val);
root->right=newNode;
}
}
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root==nullptr){//考虑没有节点的情况
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 judgeA=false;
void add(TreeNode*root,TreeNode*node){//用于删除节点时,组合该节点的两个子节点
if(node==nullptr) return;
if(root->val>node->val){//插入节点在左边
if(root->left)
add(root->left,node);
else
root->left=node;
}
else{//插入节点在右边
if(root->right)
add(root->right,node);
else
root->right=node;
}
}
void res(TreeNode*root,TreeNode*node, bool judgeB){//用于删除节点
if(judgeB)//左子节点
{
if(node->left==nullptr && node->right==nullptr){//key值节点为叶子节点
root->left=nullptr;
return;
}
else if(node->left && node->right){//key值节点有左右节点
root->left=node->right;
add(node->right,node->left);
return;
}
else if(node->left && !node->right)
root->left=node->left;
else
root->left=node->right;
}
else{
if(node->left==nullptr && node->right==nullptr){//key值节点为叶子节点
root->right=nullptr;
return;
}
else if(node->left && node->right){//key值节点有左右节点
root->right=node->right;
add(node->right,node->left);
return;
}
else if(node->left && !node->right)
root->right=node->left;
else
root->right=node->right;
}
}
void judge(TreeNode*root,int key){//用于查找删除节点
if(root==nullptr)
return;
if(root->val>key){//当父节点大于key,说明key在左边
if(root->left->val==key){//当左子节点等于key时
res(root,root->left,true);
}
else
judge(root->left,key);
}
else if(root->val<key){
if(root->right->val==key){
res(root,root->right,false);
}
else
judge(root->right,key);
}
}
void judgeMax(TreeNode*root,int key){//用于判断二叉树中是否存在目标节点
if(root==nullptr) return;
if(root->val==key) judgeA=true;
if(root->val>key) judgeMax(root->left,key);
if(root->val<key) judgeMax(root->right,key);
}
TreeNode* deleteNode(TreeNode* root, int key) {
//思路:遍历二叉树,找到节点时,判断当前节点左右两边情况
//
if(root==nullptr) return root;
if(root->val==key){
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;
else
return nullptr;
}
judgeMax(root,key);
if(judgeA==false){
cout<<123;
return root;
}
judge(root,key);
return root;
}
};
文章来源地址https://www.toymoban.com/news/detail-647719.html
文章来源:https://www.toymoban.com/news/detail-647719.html
到了这里,关于休息是不可能休息的的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!