前言❤️❤️hello hello这里是洋不写bug~欢迎大家点赞关注收藏这篇博客就到了数据结构中据说最难的部分——二叉树算法题二叉树结构的基础知识不算难难的是算法题目这部分之所以难是因为基本上这些算法都使用了递归虽然代码就那么几行但是想理解透递归的调用过程还是需要花费一些力气的博主计划一共解析14道经典的二叉树算法题目这篇博客解析7道下篇博客解析7道为了方便解析这篇博客的所有题目博主都画了递归解析图初学的铁汁强烈建议每道题目都自己画一下递归图细品下过程这个专栏的数据结构是代码都是用Java来写的JavaSE专栏现在已经全部更新完成铁汁们复习基础知识时非常推荐使用可以试一下个人主页洋不写bug的博客所属专栏数据结构专栏复习Java基础知识Java学习之旅从入门到进阶铁汁们对于数据结构基础的各种核心知识不太常用的也有都可以在上面的数据结构专栏学习专栏正在持续更新中有问题可以写在评论区或者私信我哦~1相同的树力扣链接题意就是传入两棵树的根结点判断这两棵树是否完全相等这个题目仍然可以使用递归的方法来解决可以分为以下几步判定两个树的根结点是否相同递归判定左子树是否相同递归判定右子树是否相同只要发现上面任何一个环节出现不同就返回false如果从头到尾都没有返回false就返回trueclassSolution{publicbooleanisSameTree(TreeNodep,TreeNodeq){if(pnullqnull){returntrue;}if((pnullq!null)||(p!nullqnull)){returnfalse;}if(p.val!q.val){returnfalse;}booleanisLeftSameisSameTree(p.left,q.left);booleanisRightSameisSameTree(p.right,q.right);returnisLeftSameisRightSame;}}画图分析分析下递归过程2另一棵树的子树力扣链接这个题目让我们判断subRoot是否是root的子树subRoot和root是两棵树的根结点在上个题目的基础上做这道题就简单首先判断root和subRoot是不是相同的树题目中给出了如果两个树相同subRoot也可以看作是root的子树递归判定root.left是否包含subRoot递归判定root.right是否包含subRoot只要中间有一处判定成功就返回trueclassSolution{publicstaticbooleanisSameTree(TreeNodep,TreeNodeq){if(pnullqnull){returntrue;}if(pnullq!null){returnfalse;}if(p!nullqnull){returnfalse;}if(p.val!q.val){returnfalse;}booleanisLeftSameisSameTree(p.left,q.left);booleanisRightSameisSameTree(p.right,q.right);returnisLeftSameisRightSame;}publicbooleanisSubtree(TreeNoderoot,TreeNodesubRoot){if(rootnullsubRootnull){returntrue;}if(root!nullsubRootnull){returnfalse;}if(rootnullsubRoot!null){returnfalse;}if(isSameTree(root,subRoot)){returntrue;}booleanisSubleftisSubtree(root.left,subRoot);booleanisSubRightisSubtree(root.right,subRoot);returnisSubleft||isSubRight;}}题目中已经明确指出了subRoot不为null了这里博主的代码针对的是不加限制的情况铁汁们写的时候可以把isSubtree方法刚开始的if判断少写一些这个题目如果要画图分析递归就只画isSubTree方法的递归图即可把isSameTree就当成一个普通方法即可如果同时画isSameTree和isSubTree的递归图那就会超级复杂递归过程分析如下3翻转二叉树力扣链接这个题目依旧是使用递归就是对根结点的左子结点和右子结点进行翻转接着再进行递归对根结点的左子结点的左子结点和右子结点进行翻转以及对根结点的右子结点的左子结点和右子结点进行翻转以此类推就能把整个链表翻转过来代码就是遍历二叉树访问结点时操作为交换该结点的左子结点和右子结点classSolution{publicTreeNodeinvertTree(TreeNoderoot){if(rootnull){returnnull;}TreeNodetmproot.left;root.leftroot.right;root.righttmp;invertTree(root.left);invertTree(root.right);returnroot;}}这个题目使用前序遍历和后序遍历都可以博主比较推荐使用前序遍历的写法因为比较好理解但不能使用中序遍历因为中序遍历是先针对左子树来进行递归递归完成左子树后那左子树就变成右子树再去针对右子树进行递归相当于递归的还是之前的左子树也就是左子树递归了两次classSolution{publicTreeNodeinvertTree(TreeNoderoot){if(rootnull){returnnull;}invertTree(root.left);TreeNodetmproot.left;root.leftroot.right;root.righttmp;invertTree(root.right);returnroot;}}我们画图来看下中序遍历是如何递归的可以看到是递归不到右子树上的运行到invertTree(root.right)递归的还是原来左子树的结点4平衡二叉树力扣链接平衡二叉树针对这个树的任何一个结点左右子树的高度差不超过1就认为是平衡二叉树如下图在二叉树二博客中解析了计算二叉树的高度的方法代码如下publicintgetHeight(TreeNoderoot){if(rootnull){return0;}return1Math.max(getHeight(root.left),getHeight(root.right));}使用getHeight方法先判断当前结点的左右子树的高度差有没有超过1再递归的判断左子结点和右子结点的左右子树的高度差有没有超过1就这样一直递归判断直到判断到最后一层递归是有一个结点不符合要求这棵树就不是平衡二叉树空结点或者单独一个结点都算是平衡二叉树就直接返回trueclassSolution{publicbooleanisBalanced(TreeNoderoot){if(rootnull){returntrue;}if(root.leftnullroot.rightnull){returntrue;}intleftHeightgetHeight(root.left);intrightHeightgetHeight(root.right);if(leftHeight-rightHeight1||rightHeight-leftHeight1){returnfalse;}booleanisLeftBalancedisBalanced(root.left);booleanisRightBalancedisBalanced(root.right);returnisLeftBalancedisRightBalanced;}publicintgetHeight(TreeNoderoot){if(rootnull){return0;}return1Math.max(getHeight(root.left),getHeight(root.right));}}递归分析图如下如果isBalanced里面传入的结点没有左右子树或者为null博主就不再继续往下画了直接返回true)5对称二叉树力扣链接判断对称二叉树就是判断根结点的左子树和右子树是否为镜像如下图左子树的根结点为t1右子树的根结点为t2判断镜像的方法分为以下几步判断根结点的值是否相同如果不相同就直接返回false递归判断t1.left和t2.right是否互为镜像递归判断t1.right和t2.left是否互为镜像我们写个isMirror方法传入参数是两个子树的根结点递归的来执行这些过程如果在递归过程中一直都没有返回false那isMirror方法最后就返回trueclassSolution{publicbooleanisSymmetric(TreeNoderoot){returnisMirror(root.left,root.right);}publicbooleanisMirror(TreeNodet1,TreeNodet2){if(t1nullt2null){returntrue;}if((t1!nullt2null)||(t2!nullt1null)){returnfalse;}if(t1.val!t2.val){returnfalse;}booleanisMirror1isMirror(t1.left,t2.right);booleanisMirror2isMirror(t1.right,t2.left);returnisMirror1isMirror2;}}6二叉树遍历牛客链接刷题平台上的算法题分为两种类型核心代码模式和ACM模式大部分题目都是核心代码模式前面的5道题目就都属于是核心代码模式不需要自己创建Node类不需要考虑树是怎么创建起来的有的也不需要考虑输出就需要写个方法题目中传入参数再返回一个参数即可比较简单这个题目就是ACM模式需要自己写结点类处理输入创建树在main方法中处理输入和输出要考虑的东西就比核心代码模式要多题目中说空格字符代表空树说先用“#”代表空格但是看示例输入的时候还是输入的#“描述的就不是很清楚到底是输入的时候输入的是”#“还是输入的实际是空格为了方便我们看用”#表示这个就有点歧义这个问题很好解决写代码的时候让输入空格可以输入#也可以这个题目的重点就是如何通过先序遍历的序列来构建出二叉树正常最少需要两种遍历的序列才能构建出二叉树但是这个先序遍历序列中对于空树用空格表示出来了属于特殊的先序序列就拿示例1输入的数据来举例a一定为根结点后面输入的是b铁汁们细品下有办法判断出b是a的左子结点还是a的右子结点如果是普通的前序序列这个是没法判断的但是这个前序序列用空格字符代表空树了a和b输入之间是没有空格的因此b一定是a的左子结点如果是右子结点的话输入就是a#b到c这里同理c不可能是b的右子结点输入为b#c时是这样更不可能是a的右子结点输入为b##c时是这样c一定是b的左子结点再接下来是##dc的左右子树就是#b的右子结点就是d规律就是当一个结点的左子树都构造完成再去构造这个结点的右子树按照这个规律就能构造出完整的树因为是ACM模式所以写代码时所有东西都要自己写需要定义个Node类还要考虑输入和输出题目中提到会有多组输入数据每组数据是一行字符串读取输入时就是用while(scanner.hasNextLine)输出时也有要求每个字符后面有一个空格每个输出占一行importjava.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{staticclassNode{publiccharval;Nodeleftnull;Noderightnull;publicNode(charval){this.valval;}}publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while(in.hasNextLine()){// 注意 while 处理多个 caseStringlinein.nextLine();Noderootbuild(line);inOrder(root);System.out.println();}}publicstaticNodebuild(Strings){}publicstaticvoidinOrder(Noderoot){if(rootnull){return;}inOrder(root.left);System.out.printf(root.val );inOrder(root.right);}}核心就是这个build方法里面传入字符串s应该通过charAt(index)来读取字符的就需要创建index成员变量记录读取到哪个位置了在main方法的while循环中每次读取数据后都需要把index清0在bulid方法中先用root.left build(s)递归的构建左子树再用root.right build(s)递归的构建右子树publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while(in.hasNextLine()){// 注意 while 处理多个 caseStringlinein.nextLine();Noderootbuild(line);inOrder(root);System.out.println();}}publicstaticintindex0;publicstaticNodebuild(Strings){charcs.charAt(index);if(c#||c ){returnnull;}NoderootnewNode(c);index;root.leftbuild(s);index;root.rightbuild(s);returnroot;}接着画图细品下递归过程7二叉树的层序遍历力扣链接层序遍历在二叉树(一)博客中就已经解析过就是让元素入队列出队列时进行打印再把出队列的结点的left和right也加入到队列中代码如下publicstaticvoidlevelOrder(Noderoot){if(rootnull){return;}QueueNodequeuenewArrayDeque();queue.offer(root);while(!queue.isEmpty()){Nodecurqueue.poll();System.out.printf(cur.val );if(cur.left!null){queue.offer(cur.left);}if(cur.right!null){queue.offer(cur.right);}}}但这个题目不是简单的层序遍历输出时同一层中同一层的结点输出时要放到同一个[]中因为方法的返回类型是一个二维的List不是打印按照层序来打印如果还是用普通层序遍历在元素出队列时是很难判断这个元素到底加到哪个一维List中的可以使用先序遍历创建一个level变量表示把元素加到哪个一维List中去每次递归时level 1写个levelOrderHelper方法里面传入三个参数root、level、result进行前序遍历先把root.val添加到ressult中对应的一维List中如果这个一维List还没有创建就需要先创建下接着再递归的处理root.left和root.right递归调用levelOrderHelper方法时需要level 1level的起始值为0result.get(0)相当于是树的第一层的元素classSolution{publicListListIntegerlevelOrder(TreeNoderoot){ListListIntegerresultnewArrayList();if(resultnull){returnresult;}levelOrderHelper(root,0,result);returnresult;}publicstaticvoidlevelOrderHelper(TreeNoderoot,intlevel,ListListIntegerresult){if(rootnull){return;}if(result.size()level){result.add(newArrayList());}ListIntegercurRowresult.get(level);curRow.add(root.val);levelOrderHelper(root.left,level1,result);levelOrderHelper(root.right,level1,result);}}用示例1中的树画图来模拟下递归过程结语这7道题目解决起来并不简单有的直接可以在原方法中递归解决有的需要写个Helper方法方法在Helper方法中进行递归学习这部分内容的最好方法就是画图细品自己多写几次代码然后过段时间再来写这个题目的代码看有没有完整的思路多细品代码能力一定会提升的以上就是今天的所有内容啦完结撒花