首页 > 编程语言 >算法练习-day17

算法练习-day17

时间:2023-07-10 22:32:11浏览次数:52  
标签:return int 练习 算法 day17 二叉树 root 节点 targetSum

二叉树

110. 平衡二叉树

题意:给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例:

算法练习-day17_二叉树

思路:本题我们可以自下而上判断二叉树是否为平衡二叉树,以上图为示例,我们先判断15是不是平衡二叉树,很明显是的,此时就引出了我们递归的终止条件,当root为空时,此时返回0;再判断20节点,发现高度差为0,符合条件,此时的高度变为1+子二叉树的最大高度,此时为2,以此往上判断;而当高度差大于-1时,这时我们就会有新的判断条件,只要有一个子树为-1,那么之后的所有子树都为-1,这样我们在返回主函数判断时,判断的依据也自然就是返回的值是否等于-1

递归代码:

    int BalanceAVL(TreeNode *root)
    {
        if(nullptr==root)//递归终止条件
        {
            return 0;
        }
        int leftheigh=BalanceAVL(root->left);//左子树高度
        if(leftheigh==-1)
        {
            return -1;
        }
        int rightheigh=BalanceAVL(root->right);//右子树高度
        if(rightheigh==-1)
        {
            return -1;
        }
        int heighdeffer;//节点最大高度
        if(leftheigh-rightheigh>1||leftheigh-rightheigh<-1)
        {
            heighdeffer=-1;
        }
        else
        {
            heighdeffer=1+max(leftheigh,rightheigh);
        }
        return heighdeffer;
    }
    bool isBalanced(TreeNode* root) {
        return BalanceAVL(root)!=-1?true:false;
    }

513. 找树左下角的值

题意:给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。

示例:

算法练习-day17_二叉树_02

思路:本题我们需要确定一个最大深度,因为题目给出的最左下角的值是按深度确定的,准确的是最大深度的最左侧值,因此,上图中的最左下角的值是7,而并非4。所有我们需要遍历每个叶子节点,并且递归终止条件中给出另一个条件去交换最左侧节点的值

递归代码:

    int maxheigh=INT_MIN;//最大深度
    int leftVal;
    void maxLiftVal(TreeNode* root,int tmpheigh)
    {
        if(nullptr==root->left&&nullptr==root->right)
        {
            if(maxheigh<tmpheigh)
            {
                maxheigh=tmpheigh;
                leftVal=root->val;
            }
            return;
        }
        if(root->left)
        {
            maxLiftVal(root->left,tmpheigh+1);
        }
        if(root->right)
        {
            maxLiftVal(root->right,tmpheigh+1);
        }
    }
    int findBottomLeftValue(TreeNode* root) {
        maxLiftVal(root,1);
        return leftVal;
    }

 112. 路径总和

题意:给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。叶子节点 是指没有子节点的节点。

示例:

算法练习-day17_二叉树_03

思路:本题的思路就是使用递归模拟回溯,减去目标值targetsum,当节点走到叶子节点且targetsum为0时,说明该二叉树有符合条件的路径。

首先,要将目标值统一减去根节点的值,因为每个路径都会包括根节点;其次,我们需要模拟目标值减少的操作,当走到叶子节点发现目标值不为0时,就需要将目标值加回来,然后从另一条路径再次判断。这里我也陷入了一种循环,就是我们在减完目标值后,确实需要立刻判断目标值和所处位置是否满足条件,但是我认为直接在函数中递归判断就行,但是,实际测试发现,还是需要使用if语句作为条件判断依据;这里相当于if语句判断完,整个函数就可以推出了,而继续递归判断的话,只能说明该路径满足,而递归不会停止,所以,此时代码的判断条件就变为了二叉树中,最右边路径之和是否等于目标值。

递归代码:

    bool pathRBTree(TreeNode* root,int targetSum)
    {
        if(nullptr==root->left&&nullptr==root->right)//走到根节点开始判断,是否满足条件
        {
            if(targetSum==0)
            {
                return true;
            }
            return false;
        }
        if(root->left)
        {
            targetSum-=root->left->val;//这里模拟的是回溯算法
            if(pathRBTree(root->left,targetSum))//减完目标值就需要直接判断是否满足条件
            {
                return true;
            }
            targetSum+=root->left->val;
        }
        if(root->right)
        {
            targetSum-=root->right->val;
            if(pathRBTree(root->right,targetSum))
            {
                return true;
            }
            targetSum+=root->right->val;
        }
        return false;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(nullptr==root)//根节点为空,直接判断错误
        {
            return false;
        }
        return pathRBTree(root,targetSum-(root->val));//统一不计算根节点
    }

106. 从中序与后序遍历序列构造二叉树

题意:给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

示例:

算法练习-day17_递归_04

思路:本题思路非常简单,就是利用后序遍历的特点,每个后序遍历数组的最后一个元素就是一棵树的根节点,然后再将中序遍历不断分割,这样一直递归下去,即可得到二叉树本来的样子

递归代码:

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(postorder.size()==0)//以后序遍历数组为目标,因为每次递归都会移除一个元素
        {
            return nullptr;
        }
        int rootval=postorder[postorder.size()-1];//锁定后序遍历最后一个元素,这就是根节点
        TreeNode* root=new TreeNode(rootval);
        int mid;//找到中序遍历的分割位置
        for(mid=0;mid<inorder.size();mid++)
        {
            if(inorder[mid]==rootval)
            {
                break;
            }
        }
        postorder.resize(postorder.size()-1);
        vector<int> leftinorder(inorder.begin(),inorder.begin()+mid);//分割中序遍历
        vector<int> rightinorder(inorder.begin()+mid+1,inorder.end());

        vector<int> leftpostorder(postorder.begin(),postorder.begin()+leftinorder.size());//分割后序遍历
        vector<int> rightpostorder(postorder.begin()+leftinorder.size(),postorder.end());

        root->left=buildTree(leftinorder,leftpostorder);
        root->right=buildTree(rightinorder,rightpostorder);
        return root;
    }

标签:return,int,练习,算法,day17,二叉树,root,节点,targetSum
From: https://blog.51cto.com/u_15209404/6681436

相关文章

  • 【数据结构与算法】队列算法题
    TS实现队列interfaceIQueue<T>{//入队enqueue(item:T):void;//出队dequeue():T|undefined;//队首peek():T|undefined;//是否为空isEmpty():boolean;//大小size():number;}classArrayQueue<T>implementsIQueue<T>{......
  • 【数据结构与算法】栈相关算法题(长期更新)
    TS实现栈interfaceIStack<T>{push(e:T):void;pop():T|undefined;peek():T;isEmpyt():boolean;size():number;}//implements:实现接口,一个类可以实现多个接口classArrayStack<T>implementsIStack<T>{privatedata:T[]=[];//pri......
  • 「学习笔记」KMP 算法
    前置知识前缀是指从串首开始到某个位置\(i\)结束的一个特殊子串.真前缀指除了\(S\)本身的\(S\)的前缀.举例来说,字符串abcabeda的所有前缀为{a,ab,abc,abca,abcab,abcabe,abcabed,abcabeda},而它的真前缀为{a,ab,abc,abca,abcab,abcabe,abcabed}.......
  • 算法细节系列(1):Java swap
    算法细节系列(1):Javaswap问题在C++中,swap算法可以用指针来实现,因此在Java中,如果采用如下代码来对两个数字进行交换时,也不会影响两个对象的值。publicclassTestSwap{publicstaticvoidmain(String[]args){inta=2;intb=3;System.out.prin......
  • 文心一言 VS 讯飞星火 VS chatgpt (57)-- 算法导论6.4 1题
    文心一言VS讯飞星火VSchatgpt(57)--算法导论6.41题一、参照图6-4的方法,说明HEAPSORT在数组A=(5,13,2,25,7,17,20,8,4)上的操作过程。文心一言:下面是HEAPSORT在数组A=(5,13,2,25,7,17,20,8,4)上的操作过程:调用BUILD-MAX-HEAP函数,将数组A转换为最大堆。将堆顶元......
  • c#实现SharedMatting抠图算法
    内容简介      将AlphaMatting抠图算法由c++版本移植至c#环境。主要采用OpenCV的C#版本Emgu取代c++支撑的OpenCV。 参考资料http://www.inf.ufrgs.br/~eslgastal/SharedMatting/这个网页是算法的论文介绍页,可以从该网页下载到论文原文以及测试用图以及linux下的De......
  • 图解算法数据结构
    算法复杂度1.算法复杂度旨在输入数据量N的情况下,算法的时间和空间使用情况,体现算法运行使用的时间和空间随数据大小N而增大的速度。 算法复杂度主要可以从时间,空间两个角度评价:时间:假设各操作的运行时间为固定常数,统计算法运行的计算操作的数量,以代表算法运行所需时间......
  • 使用加密算法时报错:ModuleNotFoundError: No module named ‘Crypto‘
    解决办法:安装Crypto模块,执行 pipinstallCrypto ,安装成功后,再执行命令,还是报上面的错误第一步:在python3(或者python虚拟环境)目录下的/Lib/site-packages/目录下找到crypto、crypto-1.4.1.dist-info目录,将crypto首字母改为大写,即修改名称为Crypto、Crypto-1.4.1.d......
  • python图片去重复算法
    importosfromimagededup.methodsimportPHash#pipinstallimagededupphasher=PHash()defprocess_file(img_path):#生成图像目录中所有图像的二值hash编码encodings=phasher.encode_images(image_dir=img_path)duplicates=phasher.find_duplica......
  • MFCC 算法及 C 实现
    参考https://blog.csdn.net/weixin_38468077/article/details/1027095101.MFCC是做什么?1.1梅尔频谱人耳能听到的声音频率范围是20-20000Hz,但是人耳对频率感知并不是线性的,而是近似于......