休息是不可能休息的

这篇具有很好参考价值的文章主要介绍了休息是不可能休息的。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

到了这里,关于休息是不可能休息的的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录算法训练DAY25|回溯2

    力扣题目链接 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。 说明: 所有数字都是正整数。 解集不能包含重复的组合。 示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]] 示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]

    2024年01月22日
    浏览(63)
  • 代码随想录算法训练day4 | 链表

    目录 24. 两两交换链表节点 19. 删除链表倒数第n个节点 方法一:普通写法 方法二:双指针法 面试题:找链表相交节点 142. 判断环形链表 虚拟头节点的本质意义在于减少了特殊情况的处理。不用判断该节点是否在链表的第一位。 定义快慢两个指针。 fast先走n步,再让fast和s

    2024年02月04日
    浏览(67)
  • 代码随想录算法训练DAY27|回溯3

    力扣题目链接 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明: 所有数字(包括 target)都是正整数。 解集不能包含重复的组合。 示例 1: 输入:candidates = [2,3,6,

    2024年01月23日
    浏览(58)
  • 代码随想录-回溯算法(子集问题)|ACM模式

    目录 前言: 78. 子集 题目描述: 输入输出描述: 思路和想法: 90. 子集 II 题目描述: 输入输出描述: 思路和想法: 491. 递增子序列 题目描述: 输入输出描述: 思路和想法: 如果把 子集问题、组合问题、分割问题都抽象为一棵树的话, 那么组合问题和分割问题都是收集

    2024年02月15日
    浏览(156)
  • 代码随想录算法练习Day1:二分查找

    题目链接:704. 二分查找 卡哥视频讲解:手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找 二分法概述: 二分法(Binary Search)是一种在有序数组或列表中查找目标元素的算法。 二分法使用前提 : 有序数组或列表 :二分法要求在查找的数据结

    2024年04月23日
    浏览(58)
  • 代码随想录算法训练51 | 动态规划part12

    本题加了一个冷冻期,状态就多了,有点难度,大家要把各个状态分清,思路才能清晰  视频讲解: 动态规划来决定最佳时机,这次有冷冻期!| LeetCode:309.买卖股票的最佳时机含冷冻期_哔哩哔哩_bilibili 代码随想录 相对122.买卖股票的最佳时机II ,本题只需要在计算卖出操

    2024年01月18日
    浏览(55)
  • 动态规划例题(代码随想录学习)——持续更新

    dp[i][j]的含义是:从(0,0)到(i,j)的不同路径 当路线中有了障碍,此路不通,所以在不同路径的递推公式上需要增加条件 if(obs[i,j]==0)没有障碍,dp[i][j]= dp[i-1][j]+dp[i][j-1] if(obs[i][j]==1)有障碍,不进行推导 obs数组表示障碍 障碍的后面应该是0(原因:遇到障碍后,即

    2024年04月12日
    浏览(44)
  • 代码随想录Day20 回溯算法 LeetCode77 组合问题

    以下内容更详细解释来自于:代码随想录 (programmercarl.com) 回溯法也叫回溯搜索法,是搜索法的一种,我们之前在二叉树中也经常使用到回溯来解决问题,其实 有递归就有回溯 ,有的时候回溯隐藏在递归之下,我们不容易发觉,今天我们来详细介绍一下什么是回溯,它能解决哪些问题.

    2024年02月08日
    浏览(54)
  • 【代码随想录算法第一天| 704.二分查找 27.移除元素】

    题目链接:二分查找 文章讲解:代码随想录.二分查找 视频讲解:手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找_哔哩哔哩_bilibili 二分前提:有序数组,数组中无重复元素 方法:结合数组的特征,可以为左闭右闭区间[0, 数组长度-1],或者左

    2024年02月16日
    浏览(45)
  • 代码随想录 Leetcode459. 重复的子字符串(KMP算法)

            此解法读者需要了解什么是KMP算法以及KMP算法中next数组的具体含义才能理解         因为在KMP算法的next数组中,next[index]表示 i ndex之前的最大长度的相同前缀后缀值 ,那么要判断整个字符串中是否由重复字串构成,只需要以下两个条件:         1.next[n - 1] !=

    2024年01月19日
    浏览(79)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包